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

动态规划算法

<!--EndFragment-->

作者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 = 〈x₁, x₂, ..., x_m〉和 Y = 〈y₁, y₂, ..., y_n〉为输入。

它把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 - 1)

该过程的运行时间为O（m+n）。

-------------------------------

ok，最后给出此面试第56题的代码，请君自看：

参考代码如下：

#include "string.h"

// directions of LCS generation
enum decreaseDir {kInit = 0, kLeft, kUp, kLeftUp};

// Get the length of two strings' 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, j;

// initiate the length matrix
int **LCS_length;
LCS_length = (int**)(new int[length1]);
for(i = 0; i < length1; ++ i)
LCS_length[i] = (int*)new int[length2];

for(i = 0; i < length1; ++ i)
for(j = 0; j < length2; ++ j)
LCS_length[i][j] = 0;

// initiate the direction matrix
int **LCS_direction;
LCS_direction = (int**)(new int[length1]);
for( i = 0; i < length1; ++ i)
LCS_direction[i] = (int*)new int[length2];

for(i = 0; i < length1; ++ i)
for(j = 0; j < length2; ++ j)
LCS_direction[i][j] = kInit;

for(i = 0; i < length1; ++ i)
{
for(j = 0; j < length2; ++ j)
{
if(i == 0 || j == 0)
{
if(pStr1[i] == pStr2[j])
{
LCS_length[i][j] = 1;
LCS_direction[i][j] = kLeftUp;
}
else
LCS_length[i][j] = 0;
}
// a char of LCS is found,
// it comes from the left up entry in the direction matrix
else if(pStr1[i] == pStr2[j])
{
LCS_length[i][j] = LCS_length[i - 1][j - 1] + 1;
LCS_direction[i][j] = kLeftUp;
}
// it comes from the up entry in the direction matrix
else if(LCS_length[i - 1][j] > LCS_length[i][j - 1])
{
LCS_length[i][j] = LCS_length[i - 1][j];
LCS_direction[i][j] = kUp;
}
// it comes from the left entry in the direction matrix
else
{
LCS_length[i][j] = LCS_length[i][j - 1];
LCS_direction[i][j] = kLeft;
}
}
}
LCS_Print(LCS_direction, pStr1, pStr2, length1 - 1, length2 - 1); //调用下面的LCS_Pring 打印出所求子串。

return LCS_length[length1 - 1][length2 - 1];//返回长度。
}

// Print a LCS for two strings
// Input: LCS_direction - a 2d matrix which records the direction of
// LCS generation
// pStr1 - the first string
// pStr2 - the second string
// row - the row index in the matrix LCS_direction
// col - the column index in the matrix LCS_direction
void LCS_Print(int **LCS_direction,
char* pStr1, char* pStr2,
size_t row, size_t col)
{
if(pStr1 == NULL || pStr2 == NULL)
return;

size_t length1 = strlen(pStr1);
size_t length2 = strlen(pStr2);

if(length1 == 0 || length2 == 0 || !(row < length1 && col < length2))
return;

// kLeftUp implies a char in the LCS is found
if(LCS_direction[row][col] == kLeftUp)
{
if(row > 0 && col > 0)
LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col - 1);

// print the char
printf("%c", pStr1[row]);
}
else if(LCS_direction[row][col] == kLeft)
{
// move to the left entry in the direction matrix
if(col > 0)
LCS_Print(LCS_direction, pStr1, pStr2, row, col - 1);
}
else if(LCS_direction[row][col] == kUp)
{
// move to the up entry in the direction matrix
if(row > 0)
LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col);
}
}

扩展：如果题目改成求两个字符串的最长公共子字符串，应该怎么求？

子字符串的定义和子串的定义类似，但要求是连续分布在其他字符串中。

比如输入两个字符串BDCABA和ABCBDAB的最长公共字符串有BD和AB，它们的长度都是2。

附注：算法导论上指出，

一、最长公共子序列问题的一个一般的算法、时间复杂度为O（mn）。

然后，Masek和Paterson给出了一个O(mn/lgn)时间内执行的算法，其中n<=m，而且此序列是从一个有限集合中而来。

在输入序列中没有出现超过一次的特殊情况中，Szymansk说明这个问题可在O(（n+m）lg（n+m）)内解决。

二、一篇由Gilbert和Moore撰写的关于可变长度二元编码的早期论文中有这样的应用：

在所有的概率pi都是0的情况下构造最优二叉查找树，这篇论文给出一个O（n^3）时间的算法。

Hu和Tucker设计了一个算法，它在所有的概率pi都是0的情况下，使用O（n）的时间和O（n）的空间，

最后，Knuth把时间降到了O（nlgn）。

关于此动态规划算法更多可参考 算法导论一书第15章 动态规划问题，

至于关于此面试第56题的更多，可参考我即将整理上传的答案V04版第41-60题的答案。

完、July、二零一零年十二月三十一日。

----------------------------------------------------------------------------------------------------------

补一网友提供的关于此最长公共子序列问题的java算法源码，我自行测试了下，正确：

import java.util.Random;

public class LCS{
public static void main(String[] args){

//设置字符串长度
int substringLength1 = 20;
int substringLength2 = 20; //具体大小可自行设置

// 随机生成字符串
String x = GetRandomStrings(substringLength1);
String y = GetRandomStrings(substringLength2);

Long startTime = System.nanoTime();
// 构造二维数组记录子问题x[i]和y[i]的LCS的长度
int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];

// 动态规划计算所有子问题
for (int i = substringLength1 - 1; i >= 0; i--){
for (int j = substringLength2 - 1; j >= 0; j--){
if (x.charAt(i) == y.charAt(j))
opt[i][j] = opt[i + 1][j + 1] + 1;//参考上文我给的公式。
else
opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]); //参考上文我给的公式。
}
}

-------------------------------------------------------------------------------------

理解上段，参考上文我给的公式：

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

如果我们记字符串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

-------------------------------------------------------------------------------------

System.out.println("substring1:"+x);
System.out.println("substring2:"+y);
System.out.print("LCS:");

int i = 0, j = 0;
while (i < substringLength1 && j < substringLength2){
if (x.charAt(i) == y.charAt(j)){
System.out.print(x.charAt(i));
i++;
j++;
} else if (opt[i + 1][j] >= opt[i][j + 1])
i++;
else
j++;
}
Long endTime = System.nanoTime();
System.out.println(" Totle time is " + (endTime - startTime) + " ns");
}

//取得定长随机字符串
public static String GetRandomStrings(int length){
StringBuffer buffer = new StringBuffer("abcdefghijklmnopqrstuvwxyz");
StringBuffer sb = new StringBuffer();
Random r = new Random();
int range = buffer.length();
for (int i = 0; i < length; i++){
sb.append(buffer.charAt(r.nextInt(range)));
}
return sb.toString();
}
}

eclipse运行结果为：

substring1:akqrshrengxqiyxuloqk
substring2:tdzbujtlqhecaqgwfzbc
LCS:qheq Totle time is 818058 ns

-------------------------------------------------------
-------------------------------------------------------
/*
* x_array,x_length: X序列及其长度
* y_array,y_length: Y序列及其长度
* b_array,b_length: 记录LCS的元素，b_length=min(x_length,y_length)
* 返回LCS长度
*/

int dynamic_lcs(int *x_array, int x_length,

int *y_array, int y_length,

int *b_array, int b_length)

{

int i, j, k, lcs_length;

int **c_array=NULL;

c_array = malloc(sizeof(int *)*(x_length+1));

for(i=0; i

c_array[i] = malloc(sizeof(int)*(y_length+1));

for(i=0; i

c_array[i][0] = 0;

for(j=0; j

c_array[0][j] = 0;

k = 0;

for(i=0; i

{

for(j=0; j

{

if(x_array[i] == y_array[j])

{

c_array[i+1][j+1] = c_array[i][j]+1;

b_array[k++] = x_array[i];

}

else if(c_array[i+1][j] >= c_array[i][j+1])

c_array[i+1][j+1] = c_array[i+1][j];

else

c_array[i+1][j+1] = c_array[i][j+1];

}

}

lcs_length = c_array[x_length][y_length];

for(i=0; i

free(c_array[i]);

free(c_array);

return lcs_length;

}

<!--EndFragment-->