《算法导论》读书笔记与习题解答 — 15.1 钢条切割
笔记
本节给出一个寻找钢条最优切割方案的问题。公司购买长钢条，将其切割为短钢条出售。为简化分析，假设切割过程本身没有成本，并且切割下来的短钢条长度都为一英寸的整数倍。下表给出了不同长度的钢条的价格。
钢条切割问题：给定一根长度为n英寸的长钢条，求最优切割方案，使得销售收益rn最大。注意，最优方案也有可能是完全不用切割。
长度为n英寸的钢条有2n-1种切割方案，因为在距离钢条左端i (i = 1, 2, … , n-1)英寸处，我们总是可以选择切割或不切割。但是在实际求解过程中，可以不用遍历这2n-1种切割方案，而采用某种方法可以将该问题分解为规模更小的子问题，以下是求解该问题的方法：
- 我们将钢条从左端切下长度为i的一段，其中i =1, 2, … , n，有n种切法，我们对这一段不再进行切割，该段的销售收益为pi；
- 而右端剩下的长度为n-i，对这一段再进行切割，这是一个规模更小的子问题，其销售收益为rn-˗i。
上图比较直观地展示了求解方法。显然，我们可以得到最优收益
由上面的过程，我们引出了动态规划的第一个基本特点：所求解的问题满足最优子结构，问题可以分解为规模更小的子问题，问题的最优解依赖于子问题的最优解，并且这些子问题可以独立求解。
根据上面的公式，我们自然而然地可以用递归的方式写出代码。
下图显示了CUT-ROD在n = 4时的递归树。可以看到，CUT-ROD会重复以相同的参数调用多次。例如在下图中，CUT-ROD对n = 2重复调用了2次，对n =1重复调用了4次，而对n = 0重复调用了7次。
我们来分析CUT-ROD的运行时间。令T(n)表示参数为n时CUT-ROD的调用次数。T(n)等于递归树中根为n的子树中的结点总数，因此有
令T(0) = 1，可以求解得到T(n) = 2n。所以，CUT-ROD有一个指数级别的时间复杂度。显然，CUT-ROD的时间效率是很低的，原因是相同的子问题被重复多次求解了。
为了得到一个时间效率更高的算法，我们可以对每个子问题只求解一次，并将结果保存下来。如果递归过程中再次需要子问题的解，只需要查找已保存的结果，而不必重新计算。由此我们又引出了动态规划的第二个基本特点：相同的子问题只需要求解一次，如果子问题的解会被多次引用，可以将子问题的解保存起来。下面给出相应的代码实现。
下面给出了另一种方法。与上文的“自上而下”的递归方式不同，这种方法采用的是“自下而上”的方式。任何子问题的解都只依赖于规模更小的子问题。我们可以将子问题按照规模由小到大的顺序进行求解。当求解某个子问题时，它所依赖的那些规模更小的子问题都已求解完毕，并且结果已经保存。每个子问题也只需要求解一次。
BOTTOM-TO-UP-CUT-ROD的核心实际上是一个嵌套循环，不难得出它的运行时间为O(n2)。相比于代码一的指数增长的运行时间，BOTTOM-TO-UP-CUT-ROD的运行效率大为提高。
上文给出的代码只能得到最优收益，而不能得到最优切割方案本身。我们需要在算法计算最优收益的同时，记录下最优的切割方案。下面给出代码。
练习
15.1-1 由公式(15.3)和初始条件T(0) = 1，证明公式(15.4)成立。
解
该问题实际上是要分析代码一的运行时间。
用数学归纳法。初始条件取n = 0，有T(0) = 1 = 20，显然命题对于初始条件是成立的。
现在考虑n > 0的情况。假设命题对所有1 ~ n-1的情况都成立，那么有T(n) = 1 + (1 + 21 + … + 2n-1) = 1 + (2n - 1) = 2n。命题得证。
15.1-2 举反例证明下面的“贪心”策略不能保证总是得到最优切割方案。定义长度为 i 的钢条的价格密度为pi / i，即每英寸的价格。贪心策略将长度为 n 的钢条切割下长度为 i (1 ≤ i ≤ n)的一段，其价格密度最高。接下来继续使用相同的策略切割长度为 n-i 的剩余部分。
解
还是以上文的价格表为例，可以算出每种长度的价格密度，如下表所示。
如果原始的钢条长度为4。按照贪心策略，先切下长度为3的一段，因为长度不超过4的钢条中，长度为3的钢条的价格密度最高；然后剩下一段长度为1。这种切割方式的收益为p3 + p1 = 8 + 1 = 9。而实际上最优切割方案是切割为两段长度为2的钢条，所获得的收益为10。因此，贪心策略是不可靠的。
15.1-3 我们对钢条切割问题进行一点修改，除了切割下的钢条段具有不同的价格 pi 外，每次切割还要付出固定的成本c。这样，切割方案的收益就等于短钢条的价格之和减去切割成本。设计一个动态规划算法解决修改后的钢条切割问题。
解
该问题仍然满足上文提到的最优子结构。只需对算法稍加修改，即在计算每种方案的收益时减去切割成本。因此，最优收益公式变成了 需要注意的是，不切割的方案不会有切割成本。下面的代码是在上文代码三的基础上修改的。
15.1-4 修改MEMOIZED-CUR-ROD，使之不仅返回最优收益值，还返回切割方案。
解
15.1-5 斐波那契数列可以用递归式(3.22)定义。设计一个O(n)的时间的动态规划算法计算第n个斐波那契数。
解
最简单的方法是直接采用递归的方式来计算Fn，如下面的代码所示。
该算法的运行时间满足递归式T(n) = T(n-1)+ T(n-2)，假设初始条件为T(0) = 1，T(1) = 1。我们写出从n到2的运行时间的递归式，得到以下方程组。
将方程组中的每个方程相加，消去抵消项，得到
这个递归式与习题15.1-1中要求解的递归式有几乎相同的形式，可以推断T(n) = Θ(2n)。因此，直接采用递归的方式来计算Fn，时间效率是很低下的。效率低下的原因也是重复求解了相同规模的子问题。为了提高时间效率，可以借鉴钢条切割问题中的自下而上的求解方法。
该算法的核心是从2到 n 的循环迭代，这反映了自下而上的求解方法。每次迭代 i，只需要用到前两个元素，即第 i-1 个元素和第 i-2 个元素。因此，仅需要用两个局部变量 f1 和 f2 来保存第 i-1 个元素和第 i-2 个元素，并且每次迭代后更新这两个局部变量，而无需保存从0到 n 的每个元素。显然，这个算法的时间复杂度为O(n)。
本节相关的code可以到github上下载。