4.1 动态规划基础

4.1.1 动态规划基本思想

和分治法一样，动态规划也是通过组合子问题的解而解决整个问题，但是二者的不同之处在于：分治法将问题划分成一些独立的子问题，然后递归地求解各子问题，最后合并子问题的解得到原始问题的解；而动态规划适用于子问题独立但重叠的情况，子问题独立指的是一个子问题的解不会影响同一问题中另一个子问题的解，子问题重叠指的是各个子问题中包含有公共的子问题，在这种情况下，如果用分治法来解决问题，会导致对同一个子问题进行多次重复求解，进而降低效率。动态规划的思路是在解决原始问题的过程中，对每个子问题只求解一次，将其结果保存下来，避免在后续的求解过程中重复计算。

在设计动态规划算法时，大体可以分为以下4个阶段：

1）分析最优解的性质，并形式化描述最优解的结构；

2）递归定义最优解的值；

3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值；

4）根据计算最优值时得到的信息，构造问题的最优解。

接下来将通过一个具体的例子来看如何利用动态规划思想解决一个实际问题——求解两个字符串的最长公共子序列。

4.1.2 动态规划算法举例——最长公共子序列

这一小节重点介绍使用动态规划算法解决最长公共子序列问题，通过这个例子的介绍，可以令读者对动态规划算法的设计以及应用模式有一个直观的感受，接下来再从抽象层面来分析动态规划算法的特征以及适用范围。

1.问题描述与相关概念

给出两个序列（序列中的元素可以是任意形式，例如数字或字符等）S₁和S₂，有很多种方法来度量它们之间的相似性，其中的一种度量方法为找出第三个序列S₃，S₃中的元素都出现在S₁和S₂中，而且这些元素必须是以相同的顺序出现，但不必是连续的。能找到的S₃越长，表明S₁和S₂越相似。可以把这个相似性度量方法形式化为最长公共子序列问题。在给出具体算法思路前，首先来介绍相关的几个概念。

子序列（Subsequence）：一个特定序列的子序列就是将给定序列中零个或多个元素去掉后得到的结果（不改变元素间相对次序）。以形式化的方式来说，给定序列X=＜x₁, x₂,…, x_m＞，另一个序列Z=＜z₁, z₂,…, z_k,＞是X的子序列，那么必然存在X的一个严格递增下标序列＜i₁, i₂,…, i_k,＞，使得对所有的j=1, 2,…, k，有x_ij=z_j。例如序列<A,B>、<B,C,A>、<A,B,C,D,A>都是序列<A,B,C,B,D,A,B>的子序列。

公共子序列（Common Subsequence）：给定序列X和Y，序列Z是X的子序列，也是Y的子序列，则Z是X和Y的公共子序列。例如X=<A,B,C,B,D,A,B>，Y=<B,D,C,A,B,A>，那么序列Z=<B,C,A>为X和Y的公共子序列，其长度为3。但Z不是X和Y的最长公共子序列，而序列<B,C,B,A>和<B,D,A,B>均为X和Y的最长公共子序列，长度为4，因为X和Y不存在长度大于或等于5的公共子序列。

最长公共子序列（Longest-Common-Subsequence，LCS）：给定两个序列X=＜x₁, x₂,…, x_m＞，Y=＜y₁, y₂,…, y_n＞，如何找出X和Y的最大长度公共子序列。

2.最长公共子序列解决方案

下面重点介绍如何解决最长公共子序列问题。

方法一：暴力搜索方案

暴力搜索方案主要采用的是穷举的思路，是所有算法中最直观的方法，但效率往往也是最低的。暴力搜索策略的步骤如下：

1）枚举序列X里的每一个子序列x_i；

2）检查子序列x_i是否也是序列Y里的子序列；

3）在每一步记录当前找到的子序列里面的最长的子序列。

X总共有2^m个子序列，假设枚举每个子序列需要常数时间，因此在步骤1）中枚举X中所有的子序列的时间复杂度为O(2^m)，检查每个子序列是否也是Y的子序列所需时间复杂度为O(n)。因此蛮力策略的最坏时间复杂度为O(n2^m)，这是指数级时间复杂度的算法，对较长的序列求LCS是不适用的。

方法二：动态规划方案

（1）描述一个最长公共子序列

动态规划方法的第一个步骤是描述最优解的结构特征，对于序列X=＜x₁, x₂,…, x_m＞，定义X的第i个前缀为X_i=＜x₁, x₂,…, x_i＞，例如，如果X=<A,B,C,D,A,B>，则X₃=<A,B,C>，X₀是一个空序列。对于最长公共子序列，可以用如下方式描述序列X=＜x₁, x₂,…, x_m＞和Y=＜y₁, y₂,…, y_n＞的一个最长公共子序列，假设序列Z=＜z₁, z₂,…, z_k＞是X和Y的任意一个LCS。

1）如果x_m=y_n，那么z_k=x_m=y_n，而且Z_k-1是X_m-1和Y_n-1的一个LCS；

2）如果x_m≠y_n，那么z_k≠x_m，而且Z是X_m-1和Y的一个LCS；

3）如果x_m≠y_n，那么z_k≠y_n，而且Z是X和Y_n-1的一个LCS。

以上结论的证明较为简单，读者可自行证明，此处不做过多赘述。很明显，以上的结论说明两个序列的一个LCS也包含了两个序列的前缀的一个LCS，这说明LCS问题具有最优子结构性能。因此，可以用递归的方式来描述如何寻找两个序列的LCS。

（2）一个递归解

由步骤1）中的结论可以知道，在找X=＜x₁, x₂,…, x_m＞和Y=＜y₁, y₂,…, y_n＞的一个最长公共子序列时，可能要检查一个或两个子问题。如果x_m=y_n，那么必须找出X_m-1和Y_n-1的一个LCS，再将x_m添加到这个LCS上，便可产生X和Y的一个最长公共子序列。如果x_m≠y_n，那么必须找出X_m-1和Y的一个LCS，并找出X和Y_n-1的一个LCS，这两个LCS中，较长的就是X和Y的一个最长公共子序列。因此，很显然，LCS问题具有重叠子问题的性质，即为了找出X和Y的一个最长公共子序列，可能需要找出X_m-1和Y的一个LCS，以及找出X和Y_n-1的一个LCS，但这两个子问题都包含着找出X_m-1和Y_n-1的一个LCS的子问题，还有许多其他的子问题中的共享子问题。因此，可以用一个递归式来描述和寻找LCS，设c[i, j]为序列X和Y的最长公共子序列的长度，那么有：

（3）计算LCS的长度

根据步骤2）中的递归式，可以很容易地写出一个指数时间的递归算法，来计算两个序列的LCS的长度，算法代码如下所示。过程LCS-LENGTH(X, Y)的输入为两个序列X和Y，该程序返回两个表c和b，其中c[m,n]包含X和Y的一个LCS的长度，b[i,j]指向一个表项，这个表项对应于在计算c[i,j]时所选择的最优子问题的解。

由LCS-LENGTH返回的表b可被用来快速构造X=＜x₁, x₂,…, x_m＞和Y=＜y₁, y₂,…, y_n＞的一个最长公共子序列。只需要简单地从b[m,n]开始，并按箭头方向追踪下去即可。当在表项b[i,j]中遇到一个'↖'时，意味着x_i=y_j是LCS的一个元素。按照这种方法，可以按逆序依次构造出LCS的所有元素，算法代码如下所示，其中输入参数分别为过程LCS-LENGTH返回的表b、序列X、序列X的长度以及序列Y的长度。图4-1给出了LCS-LENGTH算法在输入为序列X=<A,B,C,B,D,A,B>与序列Y=<B,D,C,A,B,A>时输出的表c和b。对于该输入，过程PRINT-LCS将输出“B C B A”。

根据本书第一部分介绍的知识，可以很容易得到算法LCS-LENGTH的运行时间为O(mn)，在算法PRINT-LCS中，因为在递归的每个阶段，i和j至少有一个要减小，由此可知算法PRINT-LCS的运行时间为O(m+n)，m和n分别为序列X和Y的长度。

其中算法输入为序列X=<A,B,C,B,D,A,B>与序列Y=<B,D,C,A,B,A>。第i行和第j列中的方块包含了c[i, j]的值以及指向b[i, j]值的箭头。