动态规划通常用于解决最优化问题，在这类问题中，通过做出一组选择来达到最优解。在做出每个选择的同时，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题时，动态规划技术通常就会很有效，其关键技术就是对每个这样的子问题都保存其解，当其重复出现时即可避免重复求解。
钢条切割问题
Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。
钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。
一、问题分析
长度为n英寸的钢条共有2n-1种不同的切割方案，因为在距离钢条左端i(i=1,2,…n)英寸处，总是可以选择切割或不切割。
如果一个最优解将钢条切割为k段（对某个
），那么最优切割方案
，将钢条切割为长度分别为i1,i2...ik的小段得到的最大收益为
。
对于
，
。其中，pn对应不切割，对于每个i=1,2,…,n-1，首先将钢条切割为长度为i和n-i的两段，接着求解这两段的最优切割收益ri和rn-i(每种方案的最优收益为两段的最优收益之和)。当完成首次切割后，我们将两段钢条看成两个独立的钢条切割问题实例。通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大者，构成原问题的最优解。
钢条切割问题还存在一种相似的但更为简单的递归求解方法：将钢条从左边切割下长度为i的一段，只对右边剩下的长度为n-i的一段继续进行切割，对左边的一段则不再进行切割。这样得到的公式为：
。这样原问题的最优解只包含一个相关子问题（右端剩余部分）的解，而不是两个。
二、算法实现
1、朴素递归算法
自顶向下递归实现参考代码为：
int CutRod(const int *p, int n) { if (n == 0) { return 0; } int q = -1; for (int i = 1; i <= n; ++i) { int tmp = CutRod(p, n - i); if (q < tmp) { q = tmp; } } return q; }
分析：自顶向下递归实现的CutRod效率很差，原因在于CutRod反复地用相同的参数值对自身进行递归调用，即它反复求解相同的子问题。它的运行时间为
。对于长度为n的钢条CutRod考察了所有2n-1种可能的切割方案。递归调用树共有2n-1个叶结点，每个叶结点对应一种可能的切割方案。
2、动态规划算法
朴素递归算法之所以效率很低，是因为它反复求解相同的子问题。因此，动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来。如果随后再次需要此子问题的解，只需查找保存的结果，而不必重新计算。因此，动态规划方法是付出额外的内存空间来节省计算空间。
动态规划有两种等价的实现方法。
（1）带备忘的自顶向下法
此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中）。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则，按通常方式计算这个子问题。
（2）自底向上法
这种方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因此，我们可以将子问题按照规模顺序，由小至大顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它时，它的所有前提子问题都已求解完成。
说明：两种方法得到的算法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自底向上方法的时间复杂度函数通常具有更小的系数。
下面给出动态规划-带备忘的自顶向下过程参考代码：
1 int MemoizedCutRodAux(const int *p, int n, int *r) 2 { 3 if (r[n] >= 0) 4 { 5 return r[n]; //首先检查所需的值是否存在 6 } 7 8 int q = -1; 9 if (n == 0) 10 { 11 q = 0; 12 } 13 else 14 { 15 for (int i = 1; i <= n; ++i) 16 { 17 int tmp = p[i] + MemoizedCutRodAux(p, n - i, r); 18 if (q < tmp) 19 { 20 q = tmp; 21 } 22 } 23 } 24 r[n] = q; 25 26 return q; 27 } 28 29 int MemoizedCutRod(const int *p, int n) 30 { 31 int *r = new int[n + 1]; 32 for (int i = 0; i <= n; ++i) 33 { 34 r[i] = -1; 35 } 36 37 return MemoizedCutRodAux(p, n, r); 38 }
下面给出动态规划-自底向上过程参考代码：
int BottomUpCutRod(const int *p, int n) { int *r = new int[n + 1]; r[0] = 0; for (int i = 1; i <= n; ++i) { int q = -1; for (int j = 1; j <= i; ++j) { int tmp = p[j] + r[i - j]; q = q > tmp ? q : tmp; } r[i] = q; } return r[n]; }
说明：自顶向下与自底向上算法具有相同的渐进运行时间
。
最后给出重构解参考代码：
1 #include <iostream> 2 using namespace std; 3 4 void ExtendedBUCutRod(const int *p, int n, int *r, int *s) 5 { 6 r[0] = 0; 7 for (int i = 1; i <= n; ++i) 8 { 9 int q = -1; 10 for (int j = 1; j <= i; ++j) 11 { 12 int tmp = p[j - 1] + r[i - j]; 13 if (q < tmp) 14 { 15 q = tmp; 16 s[i] = j; 17 } 18 } 19 r[i] = q; 20 } 21 } 22 23 //r[]保存长度为i的钢条最大收益,s[]保存最优解对应的第一段钢条的切割长度 24 void PrintBUCutRod(const int *p, int n, int *r, int *s) 25 { 26 ExtendedBUCutRod(p, n, r, s); 27 cout << "长度为" << n << "的钢条最大收益为:" << r[n] << endl; 28 29 cout << "最优方案的钢条长度分别为:"; 30 while (n > 0) 31 { 32 cout << s[n] << " "; 33 n = n - s[n]; 34 } 35 cout << endl; 36 } 37 38 //Test 39 int main() 40 { 41 int n; 42 while (cin >> n) 43 { 44 int *p = new int[n]; 45 for (int i = 0; i < n; ++i) 46 { 47 cin >> p[i]; 48 } 49 int *r = new int[n + 1]; 50 int *s = new int[n + 1]; 51 52 PrintBUCutRod(p, n, r, s); 53 } 54 55 return 0; 56 }
一个测试案例为：
原文：http://www.cnblogs.com/mengwang024/p/4342796.html