【算法】动态规划法——最长公共子序列（LCS）

绝地灬酷狼 2022-05-31 06:27 260阅读 0赞

##  ##

## 【[fishing-pan][]：[https://blog.csdn.net/u013921430][https_blog.csdn.net_u013921430]转载请注明出处】 ##

## 前言 ##

这篇是自己写的第一篇关于算法方面的博客，写他是因为自己今天打开笔记，刚好看到了它，就这么简单。

这篇博客主要想讲讲动态规划法，然后以LCS问题为例展开来说一下怎么利用动态规划法求解它，下面是自己的一些理解和总结，有不对的地方还请大家指正。

## 动态规划法 ##

动态规划法（dynamic programming）通常用于求解**最优化问题**（optimization problem），它适用于那些子问题相互重叠的情况，即子问题不独立，不同的子问题具有公共的子子问题（就是子问题的子问题）。这显然与分治法是不同的，分治法将问题划分为不重叠的子问题，然后分别求解这些子问题，最后将这些问题合并得到最终的解。

对于具有公共子问题的情况，分治法会做很多不必要的工作，它会多次求解同一子子问题。动态规划法却不一样，对每个子子问题它只会求解一次，将其保存在一个表格中，避免了不必要的重复计算。

如之前所说，动态规划法用于求解最优化问题，这就意味着可能这个问题，有很多解，但是呢，不一定都是最优解。利用动态规划法求出来的是这个问题的**一个最优解**（an optimal solution），记住这里求解的只是最优解（the optimal solution）中的一个，因为最优解可能有多个。

设计一个问题的动态规划算法主要有一下的几步

（1） 找出最优解的性质，刻画其结构特征；

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

（3） 以自底向上的方式计算出最优值；

（4） 根据计算最优解时得到的信息，构造一个最优解。

如果你只需要一个最优解的值，而不是这个结本身，就不需要第（4）步。如果你需要得到这个解本身，也就是说你需要执行第（4）步，这往往需要我们在第（3）步中记录一些额外的信息，以方便第（4）步的求解。

下面让我们来看看LCS问题如何利用动态规划法求解。

## 最长公共子序列的动态规划法实现 ##

##### 最长公共子序列（longest-common-subsequence, LCS） #####

（1）子序列：一个序列X ＝ x1x2...xn,中任意删除若干项，剩余的序列叫做A的一个子序列。也可以认为是从序列A按原顺序保留任意若干项得到的序列。  
例如：对序列 1,3,5,4,2,6,8,7来说，序列3,4,8,7 是它的一个子序列。对于一个长度为n的序列，它一共有2^n 个子序列，有(2^n – 1)个非空子序列。在这里需要提醒大家，子序列不是子集，它和原始序列的元素顺序是相关的。

（2）公共子序列：如果序列Z既是序列X的子序列，同时也是序列Y的子序列，则称它为序列X和序列Y的公共子序列。空序列是任何两个序列的公共子序列。

（3）最长公共子序列：X和Y的公共子序列中长度最长的（包含元素最多的）叫做X和Y的最长公共子序列。

这个问题如果用穷举法时间，最终求出最长公共子序列时，时间复杂度是Ο（2mn），是指数级别的复杂度，对于长序列是不适用的。因此我们使用动态规划法来求解。

##### 刻画最长公共子序列问题的最优子结构 #####

设X=x1x2…xm和Y=y1y2…yn是两个序列，Z=z1z2…zk是这两个序列的一个最长公共子序列。

1. 如果xm=yn，那么zk=xm=yn，且Zk-1是Xm-1，Yn-1的一个最长公共子序列；

2. 如果xm≠yn，那么zk≠xm，意味着Z是Xm-1，Y的一个最长公共子序列；

3. 如果xm≠yn，那么zk≠yn，意味着Z是X，Yn-1的一个最长公共子序列。

从上面三种情况可以看出，两个序列的LCS包含两个序列的前缀的LCS。因此，LCS问题具有最优子结构特征。

##### 递归的定义最优值 #####

从最优子结构可以看出，如果xm=yn，那么我们应该求解Xm-1，Yn-1的一个LCS，并且将xm=yn加入到这个LCS的末尾，这样得到的一个新的LCS就是所求。

如果xm≠yn，我们需要求解两个子问题，分别求Xm-1，Y的一个LCS和X，Yn-1的一个LCS。两个LCS中较长者就是X和Y的一个LCS。

可以看出LCS问题具有重叠子问题性质。为了求X和Y的一个LCS，我们需要分别求出Xm-1，Y的一个LCS和X，Yn-1的一个LCS，这几个字问题又包含了求出Xm-1，Yn-1的一个LCS的子子问题。（有点绕了。。。晕没晕。。。。）

根据上面的分析，我们可以得出下面的公式；

![20180209162459282][]![70][]

##### 计算最优解的值 #####

根据上面的，我们很容易就可以写出递归计算LCS问题的程序，通过这个程序我们可以求出各个子问题的LCS的值，此外，为了求解最优解本身，我们好需要一个表b，b\[i，j\]记录使C\[i，j\]取值的最优子结构。

C++代码如下；

int **Lcs_length(string X,string Y,int **B)
    {
    	int x_len = X.length();
    	int y_len = Y.length();
    
    	int **C = new int *[x_len+1];
    	for (int i = 0; i <= x_len; i++)
    	{
    		C[i] = new int[y_len + 1];        //定义一个存放最优解的值的表；
    	}
    
    	for (int i = 1; i <= x_len; i++)
    	{
    		C[i][0] = 0;
    		B[i][0] = -2;                     //-2表示没有方向
    	}
    
    
    	for (int j = 0; j <= y_len; j++)
    	{
    		C[0][j] = 0;
    		B[0][j] = -2;
    	}
    	
    	for (int i = 1; i <= x_len; i++)
    	{
    		for (int j = 1; j <= y_len; j++)
    		{
    
    			if (X[i-1]==Y[j-1])
    			{
    				C[i][j] = C[i - 1][j - 1] + 1;
    
    				B[i][j] = 0;             //0表示斜向左上
    			}
    			else
    			{
    				if (C[i-1][j]>=C[i][j-1])
    				{
    					C[i][j] = C[i - 1][j];
    					B[i][j] = -1;       //-1表示竖直向上；
    				}
    				else
    				{
    					C[i][j] = C[i][j - 1];
    					B[i][j] = 1;        //1表示横向左
    				}
    			}
    
    		}
    	}
    	return C;
    }

将C与b分别输出的记过如下图

![70 1][]

将两个表格画成一个表格的结果如下；

![20180209163048292][]

### 构造最长公共子序列 ###

从表格中可以看出，用表b中的信息可以构建出X和Y的一个LCS。从b\[m，n\]开始，沿着箭头的方向追踪，当箭头是斜上的时候，表示Xi=Yj；是LCS中的一个元素。C++代码如下；

void OutPutLCS(int **B, string X,int str1_len,int str2_len)
    {
    	
    	if (str1_len == 0 || str2_len == 0)
    	{
    		return;
    	}
    	if (B[str1_len][str2_len] == 0)   //箭头左斜
    	{
    		OutPutLCS(B, X, str1_len - 1, str2_len - 1);
    		printf("%c", X[str1_len - 1]);
    	}
    	else if (B[str1_len][str2_len] == -1)
    	{
    		OutPutLCS(B, X, str1_len - 1, str2_len);
    	}
    	else
    	{
    		OutPutLCS(B, X, str1_len, str2_len-1);
    	}
    }

最终输出的结果是BCBA，但是如之前所说，这只是所有最优解中的一个，明显BDAB也是一个最优解。

## 算法改进 ##

从方法的实现中可以看出计算LCS的过程中时间复杂度是Ο（mn），空间复杂度也是Ο（mn）。在构造最长公共子序列的过程中时间复杂度为Ο（m+n）；但是我们可以不适用表b，我们可以直接利用表C的信息构造LCS；

因为C\[i，j\]的值只依赖于三项：C\[i-1，j\]，C\[i，j-1\]，C\[i-1，j-1\]。这样就为内存节约了一个Ο（mn）空间。但是计算LCS的辅助空间并未减少，因为表C的空间复杂度依然是Ο（mn）。这部分工作利用C++很容易就能实现，我就不贴出来了。

## 再谈动态规划法 ##

通过上面的过程想必大家对于动态规划法已经有了一定的理解。对他的计算效果也肯定是非常认同的。

动态规划法是一个非常有效的算法设计技术，它主要用于具有以下两种特征的问题。

（1）最优子结构。如果一个问题的最优解中包含了其子问题的最优解，就说该问题具有最优子结构。当一个问题具有最优子结构时，我们就可以考虑使用动态规划法去实现它。

（2）重叠子问题。重叠子问题是指用来解原问题的递归算法会反复求解同样子问题，当一个递归算法不断地调用同一个问题时，就说明该问题包含了重叠子问题。此时如果用分治法求解，会反复求解同样的问题，效率低下。

## 完整代码 ##

// 动态规划法解决最长子序列.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <string>
    #include <iostream>
    
    #ifndef MAX
    #define MAX(X,Y) ((X>=Y)? X:Y)
    #endif
    
    using namespace std;
    
    int **Lcs_length(string X,string Y,int **B)
    {
    	int x_len = X.length();
    	int y_len = Y.length();
    
    	int **C = new int *[x_len+1];
    	for (int i = 0; i <= x_len; i++)
    	{
    		C[i] = new int[y_len + 1];        //定义一个存放最优解的值的表；
    	}
    
    	for (int i = 1; i <= x_len; i++)
    	{
    		C[i][0] = 0;
    		B[i][0] = -2;                     //-2表示没有方向
    	}
    
    
    	for (int j = 0; j <= y_len; j++)
    	{
    		C[0][j] = 0;
    		B[0][j] = -2;
    	}
    	
    	for (int i = 1; i <= x_len; i++)
    	{
    		for (int j = 1; j <= y_len; j++)
    		{
    
    			if (X[i-1]==Y[j-1])
    			{
    				C[i][j] = C[i - 1][j - 1] + 1;
    
    				B[i][j] = 0;             //0表示斜向左上
    			}
    			else
    			{
    				if (C[i-1][j]>=C[i][j-1])
    				{
    					C[i][j] = C[i - 1][j];
    					B[i][j] = -1;       //-1表示竖直向上；
    				}
    				else
    				{
    					C[i][j] = C[i][j - 1];
    					B[i][j] = 1;        //1表示横向左
    				}
    			}
    
    		}
    	}
    	return C;
    }
    
    void OutPutLCS(int **B, string X,int str1_len,int str2_len)
    {
    	
    	if (str1_len == 0 || str2_len == 0)
    	{
    		return;
    	}
    	if (B[str1_len][str2_len] == 0)   //箭头左斜
    	{
    		OutPutLCS(B, X, str1_len - 1, str2_len - 1);
    		printf("%c", X[str1_len - 1]);
    	}
    	else if (B[str1_len][str2_len] == -1)
    	{
    		OutPutLCS(B, X, str1_len - 1, str2_len);
    	}
    	else
    	{
    		OutPutLCS(B, X, str1_len, str2_len-1);
    	}
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	string X = "ABCBDAB";
    	string Y = "BDCABA";
    
    	int x_len = X.length();
    	int y_len = Y.length();
    
    	int **C;
    
    	int **B = new int *[x_len + 1];
    	for (int i = 0; i <= x_len; i++)
    	{
    		B[i] = new int[y_len + 1];
    	}
    
    
    	C = Lcs_length(X, Y, B);
    
    	for (int i = 0; i <= x_len; i++)
    	{
    		for (int j = 0; j <= y_len; j++)
    		{
    			cout << C[i][j]<<" ";
    		}
    		cout << endl;
    	}
    
    	cout << endl;
    
    	for (int i = 0; i <= x_len; i++)
    	{
    		for (int j = 0; j <= y_len; j++)
    		{
    			cout << B[i][j] << " ";
    		}
    		cout << endl;
    	}
    
    	OutPutLCS(B, X, x_len, y_len);
    
    	system("pause");
    	return 0;

已完。。

[fishing-pan]: https://my.csdn.net/
[https_blog.csdn.net_u013921430]: https://blog.csdn.net/u013921430
[20180209162459282]: https://img-blog.csdn.net/20180209162459282
[70]: /images/20220531/540c7a281220406b8a7b1ffca5194a51.png
[70 1]: /images/20220531/e3ca787d7be148e290c8628f13c76cd9.png
[20180209163048292]: /images/20220531/bcf9dbc7ee8448dfa1594d24c2b8c06f.png