目录
动态规划(dynamic programming)与分治方法相似，都是通过组合子问题的解来求解原问题（在这里，“programming”指的是一种表格法，并非编写计算机程序）。
分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。
动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治算法会做许多不必要的工作，它会反复求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而避免每次求解一个子子问题时都重新计算。
动态规划方法通常用来求解最优化问题(optimization problem)。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值的解。我们称这样的解为问题的一个最优解(an optimal solution)，而不是最优解(the optimal solution)，因为可能有多个解都达到最优值。
通常按如下四个步骤来设计一个动态规划算法：
- 刻画一个最优解的结构特征。
- 递归地定义最优解的值。
- 计算最优解的值，通常采用自底向上的方法。
- （回溯）利用计算出的信息构造一个最优解。——如果仅仅需要一个最优解的值，而非解本身，则不需要此步骤
15.1 钢条切割
对于长度为\(n\)英寸的钢条，共有\(2^{n - 1}\)种不同的切割方案。
对于切割长度为\(n\)英寸的钢条的最优收益\(r_n(n \geqslant 1)\)，我们可以用更短的钢条的最优切割收益来描述：
\(r_n = max(p_n, r_1 + r_{n-1}, …, r_{n-1} + r_1)\)
第一个参数\(p_n\)对应不切割直接出售长度为\(n\)英寸的钢条的方案，其他\(n - 1\)个参数对应另外\(n - 1\)种方案：对每个\(i = 1, 2, …, n - 1\)，首先将钢条切割为长度为\(i\)和\(n - i\)的两段，接着求解这两段的最优切割收益\(r_i\)和\(r_{n-i}\)——此时我们必须考察所有可能的\(i\)，选取其中最大收益者。
注意到，为了求解规模为n的原问题，我们先求解形式完全一样，但规模更小的子问题。我们称钢条切割问题满足最优子结构(optimal substructure)性质：问题的最优解由相关问题的最优解组合而成，而这些子问题可以独立求解。
我们可以将问题分解的方式简化为：将长度为\(n\)的钢条分解为左边开始一段，以及剩余部分继续分解的结果，得到简化后的公式如下（在此公式中，原问题的最优解只包含一个相关子问题的解。）：
\(r_n = max_{1 \leqslant i \leqslant n}(p_i, r_{n-i})\)
自顶向下递归实现
CUT-ROD(p, n)
1 if n == 0
2 return 0
3 q = -∞
4 for i = 1 to n
5 q = max(q, p[i] + CUT-ROD(p, n - i))
6 return q
此时，一旦输入规模稍微变大，程序运行时间会变得相当长。原因在于CUT-ROD反复地用相同的参数值对自身进行递归调用——它反复求解相同的子问题。