动态规划算法

《动态规划算法》由会员分享，可在线阅读，更多相关《动态规划算法（8页珍藏版）》请在金锄头文库上搜索。

1、经典算法研究系列：三、动态规划算法解微软一道面试题第 56题发布时间：2010-12-31 17:46动态规划算法作者 July 二零一零年十二月三十一日本文参考：微软面试100题系列V0.1版第19、56题、算法导论、维基百科。 ok,咱们先来了解下什么是动态规划算法。动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优 解能决定全局最优解（对有些问题这个要求并不能完全满足,故有时需要引入一定的近似）。 简单地说,问题能够分解成子问题来解决。动态规划算法分以下 4 个步骤：1. 描述最优解的结构2. 递归定义最优解的值3. 按自底向上的方式计算最优解的值 /此 3 步构成动

2、态规划解的基础。4. 由计算出的结果构造一个最优解。 /此步如果只要求计算最优解的值时,可 省略。好,接下来,咱们讨论适合采用动态规划方法的最优化问题的俩个要素： 最优子结构性质,和子问题重叠性质。一、最优子结构。 如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子 结构性质（即满足最优化原理）。意思就是,总问题包含很多歌子问题,而这些子问题的解也是最优的。 二、重叠子问题。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问 题并不总是新问题, 有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性 质,对每一个子问题只计算一次,然后将其计

3、算结果保存在一个表格中,当再次需要计算已经计算过的子问题时, 只是在表格中简单地查看一下结果,从而获得较高的效率。ok,咱们马上进入面试题第56题的求解，即运用经典的动态规划算法：56.最长公共子序列。 题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二 中,则字符串一称之为字符串二的子串。 注意,并不要求子串（字符串一）的字符必须连续出现在字符串二中。 请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共 子串。例如：输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的 最长公共子串，则输出它们的长度4,并打印任意一个子串。分

4、析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典 的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。 步骤一、描述一个最长公共子序列先介绍LCS问题的性质：记Xm=x0, xl,xm-l和Yn二yO,yl,，yn-1为两个 字符串,并设Zk二zO,zl,zk-l是X和Y的任意一个LCS，则可得出3条性质：1. 如果 xmT二yn-1，那么 zkT二xm-1二ynT，并且 ZkT 是 Xm-1 和 Yn-1 的一个 LCS；2. 如果 xmTHyn-l，那么当 zk-lHxmT 时，Z 是 Xm-1 和 Y 的 L

5、CS；3. 如果 xmTHyn-l，那么当 zk-lHynT 时，Z 是 X 和 Yn-1 的 LCS； 下面简单证明一下由上述相应条件得出的这些性质：1. 如果zk-lHxm-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 （xmT、yn-1）得到的 ZkT, Xm-1 和Yn-1,显然Zk-1是Xm-1和Yn-1的一个公共子串，现在我们证明Zk-1是Xm-1 和Yn-1的LCS。用反证法

6、不难证明。假设有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, xl,xm-1和 Yn二yO,yl,，yn-1的 LCS，如果xm-1二yn-1，那么只需求得Xm-1和Yn-1的LCS，并在其后添加xm-1 （yn

7、-1） 即可（上述性质1）；如果xm-lHyn-1,我们分别求得Xm-1和Y的LCS和Yn-1和X的LCS，并且这两 个LCS中较长的一个为X和Y的LCS （上述性质2、3）。根据上述结论，可得到以下公式，如果我们记字符串Xi和Yj的LCS的长度为ci,j,我们可以递归地求ci,j: / 0 if i0 or j=0 and xi=xj max（ci,j-1,ci-1,j if i,j=0 and xiHxj上面的公式用递归函数不难求得。自然想到Fibonacci第n项（本微软等100题 系列V0.1版第19题）问题的求解中可知，直接递归会有很多重复计算，所以，我们用从底向上循环求解的思路效率

8、更高。 为了能够采用循环求解的思路，我们用一个矩阵（参考下文文末代码中的LCS_length）保存下来当前已经计算好了的ci,j,当后面的计算需要这些数据时就可以直接从矩阵读取。另外，求取ci,j可以从ci-l,j-l、ci,j-l或者ci-l,j三个方向计算 得到，相当于在矩阵LCS_length中是从ci-l,j-l, ci,j-l或者ci-l,j的某一个 各自移动到ci,j,因此在矩阵中有三种不同的移动方向：向左、向上和向左上方，其中只有向左上 方移动时才表明找到LCS中的一个字符。于是我们需要用另外一个矩阵(参考下文文末代码中的LCS_direction)保存移 动的方向。步骤三，计算

9、LCS的长度LCS-LENGTH(X, Y)1 m leng thX2 n leng thY3 for i - 1 to m4 do ci, 0 - 05 for j - 0 to n6 do c0, j - 07 for i - 1 to m8 do for j - 1 to n9 do if xi = yj10 then ci, j - ci - 1, j - 1 + 111 bi, j 、12 else if ci - 1, j三 ci, j - 113 then ci, j - ci - 1, j14 bi, j t15 else ci, j - ci, j - 116 bi, j -

10、 -17 return c and b此过程 LCS-LENGTH 以俩个序列 X =x, x, x和 Y =y, y,1 2 m 1 2y为输入。n它把ci, j值填入一个按行计算表项的表c0 - m, 0 - n中，它还维护 b1m, 1n以简化最优解的构造。从直觉上看，bi, j指向一个表项，这个表项对应于与在计算ci, j时所选 择的最优子问题的解是相同的。该程序返回表中b and c， cm, n包含X和Y的一个LCS的长度。步骤四，构造一个LCS，PRINT-LCS(b, X, i, j)1 if i = 0 or j = 02 then return3 if bi, j = 4

11、then PRINT-LCS(b, X, i - 1, j - 1)5 print xi6 elseif bi, j = t7 then PRINT-LCS(b, X, i - 1, j)8 else PRINT-LCS(b, X, i, j - 1) 该过程的运行时间为 O(m+n)。ok,最后给出此面试第56题的代码，请君自看：参考代码如下：#include string.h/ directions of LCS generationenum decreaseDir kInit = 0, kLeft, kUp, kLeftUp;/ Get the length of two strings

12、 LCSs, and print one of the LCSs / Input: pStr1 - the first string/ pStr2 - the second string/ Output: the length of two strings LCSs int LCS(char* pStr1, char* pStr2) if(!pStr1 | !pStr2) return 0;size_t length1 = strlen(pStr1);size_t length2 = strlen(pStr2); if(!length1 | !length2)return 0;size_t i

13、, j;/ initiate the length matrixint *LCS_length;LCS_length = (int*)(new intlength1); for(i = 0; i length1; + i)LCS_lengthi = (int*)new intlength2; for(i = 0; i length1; + i) for(j = 0; j length2; + j)LCS_lengthij = 0;/ initiate the direction matrixint *LCS_direction;LCS_direction = (int*)(new intlength1); for( i = 0; i length1; + i)LCS_directioni = (int*)new intlength2; for(i = 0; i length1; + i) for(j = 0; j length2; + j)LCS_directionij = kInit;for(i = 0; i length1; + i)for(j = 0; j LCS_lengthi