动态规划

   动态规划方法通常用来求解最优化问题。

1. 基本原理

    什么问题应该用动态规划方法来求解呢？

1.    适合应用动态规划方法求解的最优化问题应该具备两个要素：最优子结构和重叠子问题。

2. 1.1 最优子结构

3.    如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。使用动态规划算法时，我们用子问题的最优解来构造原问题的最优解。在动态规划方法中，我们通常自底向上的使用最优子结构。也就是说，首先求得子问题的最优解，然后求原问题的最优解。原问题最优解的代价通常是子问题最优解的代价再加上由此次选择产生的代价。

4. 1.2 重叠子问题

5.    适用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须足够小，即问题的递归算法会反复求解相同的子问题，而不是一直生成新的子问题。如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。动态规划算法通常这样利用重叠子问题性质：对每个子问题求解一次，将解存入一个表中，当再次需要这个子问题时直接查表，每次查表的代价为常亮时间。

6. 1.3 基本步骤

    我们通常按照如下4个步骤来设计一个动态规划算法：

• 刻画一个最优解的结构特征。
• 递归地定义最优解得结构特征。
• 计算最优解得值，通常采用自底向上的方法。
• 利用计算出的信息构造一个最优解。

2.钢条切割问题

    题目是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,3…n)，求钢条切割方案，使得收益最大。注意，如果长度为n英寸的钢条价格足够大，最优解可能就是完全不需要切割。下图是一个价格表的样例：

我们将钢条从左边切割下长度为i的一段，只对右边剩下的长度为n-i的一段继续切割，对左边的一段不再进行切割。即问题的分解方式为：将长度为n的钢条分解为左边开始一段及剩余部分继续分解的结果。不做任何切割的方案：第一段为n，收益为，剩余部分长度为0，收益。于是得到最优解的结构特征：