前言

动态规划是算法中的一大类，是一个求解最优解的值的问题

本文内容主要来自于《算法导论第三版第四部分第15章动态规划》

四个基本步骤

我们通常需要四个步骤来设计一个动态规划算法：

1.刻画一个最优解的结构特征
2.递归地定义最优解的值。
3.计算最优解的值，通常采用自定向上的算法
4.利用计算出的信息构造一个最优解

钢条切割问题

问题描述

给定一段长度为n的英寸的钢条，和一个价格表pi（i=1,2,…,n）,求切割钢条的切割方案，是的销售收益rn最大。（如果长度为n英寸的钢条价格pn足够大，最优解可能就是完全不需要切割）

问题处理

长度为n英寸的钢条共有2^(n-1)种不同的切割方案，因为在距离钢条左端i（i=1,2,…,n-1）英寸的地方，我们总是可以选择切割或者不切割。这时候rn=max(pn,r1+r[n-1],r2+r[n-2],r[n-1]+r1)，相当于，我们将问题分割了，首先将钢条切割了，切割成了长度为i和n-i的两端，然后求解这两端的ri和r[n-i]

这样，我们就能通过组合两个相关子问题的最优解，并在所有可能的两端切割方案中选取组合收益的最大者，构成原问题的最优解。这样，我们称钢条切割问题满足最优子结构（optimal substructure）的性质：问题的最优解由相关问题的最优解组合而成，而这些子问题可以独立求解。

除此之外，我们可以将钢条从左边切割下长度为i的一段，然后只对右边剩下的长度为n-i的一段继续进行切割（递归求解），对左边的一段则不再进行切割，

而不做任何切割的方案，可以描述为：第一段的长度为n，收益为pn，剩余部分的长度为0，对应的收益为r0=0。

伪代码实现（自顶向下的方法）

	CUT-ROD（p,n)
	1	if n == 0
	2		return 0;
	3 	q = min_num
	4 	for i = 1 to n
	5 		q=max(q,p[i]+CUT-ROD(p,n-i))
	6 return q

CUT-ROD优化

上方的方法，在n变大的时候，程序运行时间会变得特别特别慢，原因是，它会反复的使用相同的参数值，对自身进行递归调用，等价于他在反复求解相同的子问题。如果将上面函数的递归调用树画出来，将会有2^(n-1)个叶节点。全部展开，必将成为一个指数级增长的趋势。上面的朴素递归算法，效率低，就是这个问题，反复求解了相同的子问题。

因此，动态规划要求仔细安排求解的顺序，对每个子问题，之求解一次，并将结果保存下来。因此，对于每个子问题的解，咱们只求一次，并且将结果保存下来，之后再遇到相同的子问题，就可以直接求出解，因此，动态规划方法，就是付出了额外的内存空间，来节省计算时间，这就是典型的时空权衡的例子。下面是两个优化算法的伪代码

带备忘的自顶向下法（top-down with memoization）

过程会保存每个子问题的解，通常保存在一个数组或者散列表当中。当需要一个子问题的解的时候，首先检查一下是否已经保存过此解。

	MEMOIZED-CUT-ROD(p,n)
	1 let r[0..n]be a new array
	2 for i = 0 to n
	3 	r[i] = min_num
	4 return MEMOIZED-CUT-ROD-AUX(p,n,r);

	MEMOIZED-CUT-ROD-AUX(p,n,r)
	1 if r[n]>=0
	2 	return r[n]
	3 if n == 0
	4 	q = 0
	5 else q = min_num
	6		for i = 1 to n 
	7 			q=max(q,p[i]+MEMOIZED-CUT-ROD-AUX(p,n-i,r))
	8 r[n]=q
	9 return q

自底向上的方法

	BOTTOM-UP-CUT-ROD(p,n)
	1 let r[0..n] be a new array
	2 r[0] = 0
	3 for j = 1 to n 
	4 		q=min_num
	5		for i = 1 to j
	6  			q = max(q,p[i]+r[j-i])
	7 		r[j]=q
	8 return r[n]

结语

算法之大，博大精深，吾之所见，沧海一粟
路漫漫其修远兮，吾将上下而求索