经典算法研究系列：三、动态规划算法解微软一道面试题[第56题]

动态规划算法

作者 July 二零一零年十二月三十一日

本文参考：微软面试100题系列V0.1版第19、56题、算法导论、维基百科。

ok，咱们先来了解下什么是动态规划算法。

动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解

(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。

简单地说，问题能够分解成子问题来解决。

动态规划算法分以下4个步骤：

1.描述最优解的结构

2.递归定义最优解的值

3.按自底向上的方式计算最优解的值 //此3步构成动态规划解的基础。

4.由计算出的结果构造一个最优解。 //此步如果只要求计算最优解的值时，可省略。

好，接下来，咱们讨论适合采用动态规划方法的最优化问题的俩个要素：

最优子结构性质，和子问题重叠性质。

一、最优子结构。

如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。

意思就是，总问题包含很多歌子问题，而这些子问题的解也是最优的。

二、重叠子问题。

子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，

有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，

然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，

从而获得较高的效率。

ok，咱们马上进入面试题第56题的求解，即运用经典的动态规划算法：

56.最长公共子序列。
题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，
则字符串一称之为字符串二的子串。

注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。
请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。
例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，
则输出它们的长度4，并打印任意一个子串。

分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，

因此一些重视算法的公司像MicroStrategy都把它当作面试题。

步骤一、描述一个最长公共子序列

先介绍LCS问题的性质：记Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}为两个字符串，

并设Zk={z0,z1,…zk-1}是X和Y的任意一个LCS，则可得出3条性质：

1.       如果xm-1=yn-1，那么zk-1=xm-1=yn-1，并且Zk-1是Xm-1和Yn-1的一个LCS；
2.       如果xm-1≠yn-1，那么当zk-1≠xm-1时，Z是Xm-1和Y的LCS；
3.       如果xm-1≠yn-1，那么当zk-1≠yn-1时，Z是X和Yn-1的LCS；

下面简单证明一下由上述相应条件得出的这些性质：
1. 如果zk-1≠xm-1，那么我们可以把xm-1（yn-1）加到Z中得到Z’，这样就得到X和Y的一个长度为k+1的公共子串Z’。

这就与长度为k的Z是X和Y的LCS相矛盾了。因此一定有zk-1=xm-1=yn-1。
既然zk-1=xm-1=yn-1，那如果我们删除zk-1（xm-1、yn-1）得到的Zk-1，Xm-1和Yn-1，显然Zk-1是Xm-1和Yn-1的一个公共子串，现在我们证明Zk-1是Xm-1和Yn-1的LCS。用反证法不难证明。假设有Xm-1和Yn-1有一个长度超过k-1的公共子串W，那么我们把加到W中得到W’，那W’就是X和Y的公共子串，并且长度超过k，这就和已知条件相矛盾了。
2. 还是用反证法证明。假设Z不是Xm-1和Y的LCS，则存在一个长度超过k的W是Xm-1和Y的LCS，那W肯定也X和Y的公共子串，而已知条件中X和Y的公共子串的最大长度为k。矛盾。
3. 证明同2。

步骤二、一个递归解

根据上面的性质，我们可以得出如下的思路：

求两字符串Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}的LCS，

如果xm-1=yn-1，那么只需求得Xm-1和Yn-1的LCS，并在其后添加xm-1（yn-1）即可（上述性质1）；

如果xm-1≠yn-1，我们分别求得Xm-1和Y的LCS和Yn-1和X的LCS，并且这两个LCS中较长的一个为X和Y的LCS（上述性质2、3）。

根据上述结论，可得到以下公式，

如果我们记字符串Xi和Yj的LCS的长度为c[i,j]，我们可以递归地求c[i,j]：

          /      0                               if i<0 or j<0
c[i,j]=          c[i-1,j-1]+1                    if i,j>=0 and xi=xj
                max(c[i,j-1],c[i-1,j]           if i,j>=0 and xi≠xj

上面的公式用递归函数不难求得。自然想到Fibonacci第n项(本微软等100题系列V0.1版第19题）问题的求解中可知，

直接递归会有很多重复计算，所以，我们用从底向上循环求解的思路效率更高。

为了能够采用循环求解的思路，我们用一个矩阵（参考下文文末代码中的LCS_length）保存下来当前已经计算好了的c[i,j]，

当后面的计算需要这些数据时就可以直接从矩阵读取。

另外，求取c[i,j]可以从c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三个方向计算得到，

相当于在矩阵LCS_length中是从c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一个各自移动到c[i,j]，

因此在矩阵中有三种不同的移动方向：向左、向上和向左上方，其中只有向左上方移动时才表明找到LCS中的一个字符。

于是我们需要用另外一个矩阵（参考下文文末代码中的LCS_direction）保存移动的方向。

步骤三，计算LCS的长度

LCS-LENGTH(X, Y)
1 m ← length[X]
2 n ← length[Y]
3 for i ← 1 to m
4      do c[i, 0] ← 0
5 for j ← 0 to n
6      do c[0, j] ← 0
7 for i ← 1 to m
8      do for j ← 1 to n
9             do if xi = yj
10                   then c[i, j] ← c[i - 1, j - 1] + 1
11                        b[i, j] ← "↖"
12                   else if c[i - 1, j] ≥ c[i, j - 1]
13                           then c[i, j] ← c[i - 1, j]
14                                b[i, j] ← "↑"
15                           else c[i, j] ← c[i, j - 1]
16                                b[i, j] ← ←
17 return c and b

此过程LCS-LENGTH以俩个序列X = 〈x1, x2, ..., xm〉和 Y = 〈y1, y2, ..., yn〉为输入。

它把c[i，j]值填入一个按行计算表项的表c[0 ‥ m, 0 ‥ n] 中，它还维护b[1 ‥ m, 1 ‥ n] 以简化最优解的构造。

从直觉上看，b[i, j] 指向一个表项，这个表项对应于与在计算 c[i, j]时所选择的最优子问题的解是相同的。

该程序返回表中 b and c ， c[m, n] 包含X和Y的一个LCS的长度。

步骤四，构造一个LCS，

PRINT-LCS(b, X, i, j)
1 if i = 0 or j = 0
2     then return
3 if b[i, j] = "↖"
4     then PRINT-LCS(b, X, i - 1, j - 1)
5          print xi
6 elseif b[i, j] = "↑"
7    then PRINT-LCS(b, X, i - 1, j)
8 else PRINT-LCS(b, X, i, j -

补充：软件开发 , C语言 ,