4.3 动态规划算法的应用

这一节，将通过几个经典的问题进一步为大家展示动态规划思想的灵活运用。其中包括动态规划解0-1背包问题，动态规划解最优二叉树。最后给出常见的一些可用动态规划思想解决的问题。

4.3.1 0-1背包问题

问题描述：小偷有一个可承受W重量的背包，他来到一户人家，发现家里有n件物品，第i个物品价值v_i且重W_i，现在小偷要从这些物品中选出总重量不超过W的物品，使其总价值最大，那么小偷应该选择哪些物品？

示例：

若n=5，W=10时，5件物品的重量与价值分别为<1,5>，<2,4>，<3,3>，<4,2>，<5,1>。

解：小偷应该带走物品1,2,3,4。所选物品总价值为14。

分析：

可以将上面的问题形式化为以下数学问题，即：找到x_i使得对于所有的x_i={0,1}, i=1, 2,…, n，使得并且最大。

现在按照前两节介绍的思路，来找出这个问题的最优子结构。首先考虑总重量不超过W的物品组合中价值最高的一组，如果把物品j从背包中拿出来，那么剩下要装载的物品一定是取自n-1个物品使得不超过载重量W -w_j并且所装物品价值最高。

令P(i,w)表示前i件物品所能获得的最高价值，其中w是背包的承受力。那么对于每一个物品i，都有两种情况需要考虑：

情况1：物品i的重量w_j≤W，小偷对物品i可拿或者不拿，那么：

P(i, w)=max{P(i-1, w), P(i-1,W-w_i)+v_i}

情况2：物品i的重量w_j＞W，那么小偷不能拿物品i，那么：

P(i, w)=P(i-1, w)

可以很容易地写出该问题的递归解：

算法分析：

基于以上的递归式，采用动态规划自下而上的方法，得到以下算法。

假设W=5，物品信息如下：

那么根据上面给出的算法Knapsack(n,w,S)可得：

4.3.2 石子归并

问题描述：在一条直线上摆着n堆石子，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分，试设计一个算法，计算出将n堆石子合并成一堆的最小得分。

示例：

假设现在有4堆石子，每一堆的石子数量分别为（4,5,9,4），依次挨着摆放。那么合并石子得分最小的方法应该是：

1）合并数量为4和5的石子堆，（（4,5）,9,4）→（9,9,4）本次得分9

2）合并数量为9和4的石子堆，（9,（9,4））→（9,13）本次得分13

3）合并目前仅有的两堆石子，（9,13）→（22）本次得分22

那么，这种合并方法的得分即为每次合并得分之和，即9+13+22=44。

分析：

如果n-1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的n-1次合并后的得分总和必然是最优的。因此可以通过动态规划思想来求解这个问题。

设m(i, j)表示将第i堆石子到第j堆石子合并后的最少总分数。a(i)为第i堆石子的石子数量，sum(i,j)表示将第i堆石子到第j堆石子合并为一堆时最后一次合并的分数，即：sum(i,j)=a(i)+a(i+1)+…+a(j)。那么：

1）当合并的石子堆为1堆时，m(i, j)=0；

2）当合并的石子堆为2堆时，只有一种合并方式，m(i, i+1)=a(i)+a(i+1)；

3）当合并的石子堆为3堆时，有两种合并方式，一种为先合并第1和第2堆，一种为先合并第2和第3堆，最优方案为这两种合并方法中分数较小的那种，因此有：

m(i, i+2)=min{(m(i,i+1)+m(i+2, i+2)+sum(i, i+2),(m(i,i)+m(i+1, i+2)+sum(i, i+2))}

4）当合并的石子堆为4堆时……

以此类推，可以知道要求m(i, j)，可以首先将这些石子堆划分成两部分，一部分从第i堆到第k堆，另一部分从第k+1堆到第j堆，合并这两部分的最小得分再加上合并这两部分的得分，就可以得到合并所有石子堆的得分。那么就要从所有的划分中找出令整体得分最小的选择（即选择令整体得分最小的k），因此，可以分析出该问题对应的递归解为：

利用上面给出的递归式可以用自底向上的方式给出算法。

算法如下：

优化：上面介绍的动态规划算法在数据规模较小时完全可以解答该问题，但是如果现在给定n的范围扩大到1≤n≤50000，那么会发生什么情况呢？首先要开辟一个50000×50000的数组来存放计算过程中的结果，这是不可行的，此外，动态规划算法的运行时间为n的二次方，在数据量大到一定程度时，运行时间无法满足要求。此时就需要重新考虑新的解法来满足超大数据范围时的时间与空间限制。

The Art of Computer Programming第3卷6.2.2节中介绍的Garsia-Wachs算法可以把当前算法的时间复杂度压缩到O(nlogn)，具体的算法细节有兴趣的读者可以阅读该书了解。这一改进的主要思想是：

现在来举例说明这一优化。假设当前排成一排的石子堆有5堆，从头到尾每一堆的石子数量依次为186、64、35、32和103。那么首先按照优化思想，去逐步对序列<A[-1] 186 6435 32 103 A[n]>进行操作，具体步骤如下。

有兴趣的读者可以亲自动手验证用动态规划与Garsia-Wachs算法得到的结果是否一致。

问题扩展1：将“在一条直线上摆着n堆石子”改为“石子是排成圆形”，其余条件不变。这个问题如何去解，留给读者自己来试一试。

问题扩展2：将“计算出将n堆石子合并成一堆的最小得分”改为“计算出将n堆石子合并成一堆的最大得分”，其余条件不变。这个问题如何去解，留给读者自己来试一试。

4.3.3 常用动态规划类问题

动态规划法经常在程序员面试中被考察，常见的动态规划类问题有如下一些内容。

1）经典问题：钢条切割、矩阵连乘、最优二叉树、Fibonacci数列。

2）字符串相关问题：编辑距离、最长回文串、最长回文子序列、回文分割、最长公共子序列、最长公共子串、行编辑问题。

3）0-1背包问题及其拓展问题：0-1背包、部分背包、全然背包、多重背包、硬币交互、子集和、子集分割问题。

4）其他问题：子数组最大和、二维子数组最大和、最长递增子序列、丑数。

前面已经给出了几种问题的具体分析与算法，下面将简要给出另外几种常见问题的递归解，如何将递归解用动态规划自底向上的方法进行实现，将留给读者们作为练习。

1.从数字三角形中找一条从顶到底的最小路径

如下代码所示为一个数字三角形，请设计算法计算从顶到底的某处的一条路径，使该路径所经过的数字总和最小。（只要求输出总和）

规定如下：

1）一步可沿左斜线向下或向右斜线向下走；

2）图形行数小于等于100；

3）三角形中的数字为0，1，…，99。

递归解：设该三角形一共有n行，f(i, j)表示从位置(i, j)出发路径的最小和，v(i, j)为位置(i, j)上数字的取值，则有：

2.求最大子数组和

给定一个整型数组a，求出最大连续子段之和，如果和为负数，则按0计算，比如1，2，-5，6，8则输出14。

递归解：假设给定数组为vec[]，设dp[i]是以vec[i]结尾的子数组的最大和，那么对于元素vec[i+1]有两种选择：

1）vec[i+1]接着前面的子数组构成最大和；

2）vec[i+1]自己单独构成子数组。

那么，可以得到递归解：dp[i+1]=max{dp[i]+vec[i+1], vec[i+1]}

3.判断字符串s3是否由s1和s2交叉存取组成

判断s3是否由s1和s2合并而成，s1和s2可以混合，但不打乱它们原来的顺序，例如s1="aabcc"，s2="dbbca"，当s3="aadbbcbcac"，返回true，当s3="aadbbbaccc"，返回false。

递归解：首先假设s1、s2和s3的长度分别为len1、len2和len3。用dp[i, j]表示s3[1,i+j]是否由s1[1,i]和s2[1, j]交错组成。如果存在len1+len2≠len3，那么答案必然为false。因此下面考虑的是如果len1+len2=len3时需要如何判断。

如果三个字符串均为空串，那么空串与空串组合，自然还是空串，因此必然有dp[0,0]=true。如果字符串非空，那么假设dp[i, j]=true，那么必然有s1_i-1=s3_i-1+j或s2_i-1=s3_i-1+j成立。

1）如果s1_i-1=s3_i-1+j，那么如果dp[i-1, j]=true，则表示s3[1,i-1+j]由s1[1,i-1]和s2[1, j]交错组成，那么很显然dp[i, j]=true，如果dp[i-1, j]=false，那么同理，dp[i, j]=false，即dp[i, j]=dp[i-1, j]。

2）如果s2_i-1=s3_i-1+j，与情况1）同理，我们可以得到dp[i, j]=dp[i, j-1]。

可以看出dp[i, j]子问题就是dp[i-1, j]或者dp[i, j-1]。如果dp[i, j]成立，必然有至少一个子问题成立。通过以上分析，我们可以得到以下递归解：