430-动态规划算法-LCS最长公共子序列

灰太狼 2022-09-05 05:15 109阅读 0赞

## LCS最长公共子序列 ##

**LCS：求两个序列的最长公共子序列的长度  
子串（字符必须是连续的）  
但是 子序列不一定是连续的**  
例如：  
**helloworld  
hlweord**  
这2个子序列的最长公共子序列是： hlweord

**我们要求**  
X : X1,X2…Xn  
Y: Y1,Y2…Ym  
**求两个序列的LCS最长公共子序列长度**  
**我们进行子问题的划分**

## 我们先用分治算法来解决 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**我们看看算法的思维图解：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**继续划分，我们发现会出现子问题的重复求解！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

**子问题重叠了，被重复求解，所以，我们应该使用动态规划算法去解决，动态规划算法对子问题的求解是有记忆性的！**

## 递归版本的动态规划求解 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**我们是从后往前推的哦**

static int cnt = 0;//用于代码测试
    
    string str1 = "helloworld";
    string str2 = "hlweord";
    int **dp = nullptr;//记录最长子序列的长度
    int **path = nullptr;//记录最长子序列的路径
    
    
    //递归实现
    int LCSA(string X, int n, string Y, int m) 
    {
        
    	if (n < 0 || m < 0)//递归结束的条件
    	{
        
    		return 0;//没有公共子序列，长度是0
    	}
    
    	if (dp[n][m] >= 0) 
    	{
           //查表，查子问题的解是否被求过
    		return dp[n][m];//直接返回问题的解，不重复求解
    	}
    
    	cnt++;//分治算法：628次    动态规划：40次
    
    	if (X[n] == Y[m]) 
    	{
        
    		dp[n][m] = LCS01(X, n - 1, Y, m - 1) + 1;
    		path[n][m] = 1;//表示n,m 跑向 n-1,m-1 1表示走对角线(左上角)
    		return dp[n][m];
    	}
    	else 
    	{
        
    		int len1 = LCS01(X, n, Y, m - 1);
    		int len2 = LCS01(X, n - 1, Y, m);
    		if (len1 >= len2) 
    		{
        
    			dp[n][m] = len1;
    			path[n][m] = 2;// n,m跑向n,m-1  2表示表示走左边
    		}
    		else 
    		{
        
    			dp[n][m] = len2;
    			path[n][m] = 3;// n,m 跑向n-1,m  3表示走上方
    		}
    		return dp[n][m];
    	}
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]

**dp数组的打印结果是：**  
\*代表的是-1  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
这个二维数组只是记录了相应的2个子串的LCS最长公共子序列的长度

**我们还要记得释放dp这个二维数组的堆内存哦！**  
**path数组打印的结果是：**  
这个二维数组记录了相应的2个子串的LCS最长公共子序列的字符![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]  
**我们根据path的定义**  
我们从最后一行最后一列的位置（右下角）开始走！！！  
**1：走对角线（左上）  
2：走左边  
3：走正上方**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]  
**因为对角线是代表：字符相比较是相等的，所以我们看往对角线走的地方，这些地方是相应元素字符相等的地方！！！**  
对角线的元素组成的字符串是：hlword，这个就是最长公共子序列！！！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]

## 非递归版本的动态规划求解 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

**我们需要用二维的dp数组来求解。**  
**因为我们需要记录3个变量，两个串和序列的长度**

**状态**：给定的两个序列的LCS的长度  
dp\[n\]\[m\] : n表示第一个串的长度 m表示第二个串的长度，n行m列元素的值，记录的就是这两个串的LCS长度  
**非递归是从0行0列开始计算的**

#include <iostream>
    #include <algorithm>
    #include <string>
    using namespace std;
    
    static int cnt = 0;//用于代码测试
    
    string str1 = "helloworld";
    string str2 = "hlweord";
    int **dp = nullptr;
    int **path = nullptr;//记录最长子序列
    
    //非递归实现
    int LCSB(string X, int i, string Y, int j) 
    {
        
    	for (int n = 1; n <= i+1; ++n)//因为n-1不能为负数 所以从1开始 然后n<=i+1，也可以是：m==n==0的时候，直接置为1
    	{
        
    		for (int m = 1; m <= j+1; ++m)//因为m-1不能为负数 所以从1开始 然后m<=j+1
    		{
        
    			if (X[n-1] == Y[m-1]) 
    			{
        
    				dp[n][m] = 1 + dp[n - 1][m - 1];//n==0 m ==0 走对角线
    				path[n][m] = 1;
    			}
    			else 
    			{
        
    				int len1 = dp[n-1][m];//向上面走
    				int len2 = dp[n][m-1];//向左边走
    				if (len1 >= len2) 
    				{
        
    					dp[n][m] = len1;
    					path[n][m] = 3;
    				} 
    				else 
    				{
        
    					dp[n][m] = len2;
    					path[n][m] = 2;
    				}
    			}
    		}
    	}
    	return dp[i+1][j+1];
    }
    
    void backStrace(string str1, int n, int m)//打印最长公共子串
    {
        
    	if (n <= 0 || m <= 0)//递归结束条件
    	{
        
    		return;
    	}
    
    	if (path[n][m] == 1) 
    	{
           //对应位置的元素是相等的
    		backStrace(str1, n - 1, m - 1);//向对角线递归
    		cout << str1[n-1];//回溯的时候再打印
    	}
    	else 
    	{
        
    		if (path[n][m] == 2) 
    		{
        
    			backStrace(str1, n, m - 1);//向左边递归
    		}
    		else 
    		{
           //path[n][m] = 3
    			backStrace(str1, n - 1, m);//向上方递归
    		}
    	}
    }
    int main()
    {
        
    	//dp是一个n行m列的二维数组
    	int n = str1.size();
    	int m = str2.size();
    	dp = new int*[n+1];//n行
    	for (int i = 0; i < n+1; ++i) 
    	{
        
    		dp[i] = new int[m+1];//m列
    		for (int j = 0; j < m+1; ++j) 
    		{
        
    			//dp[i][j] = -1;
    			dp[i][j] = 0;//初始化为0
    		}
    	}
    	path = new int*[n+1];//n行
    	for (int i = 0; i < n+1; ++i) 
    	{
        
    		path[i] = new int[m+1]();//m列
    	}
    
    	int size = LCS(str1, n-1, str2, m-1);
    	cout << "LCS length:" << size << endl;
    	cout << "cnt:" << cnt << endl;
    
    	//backStrace(str1, n-1, m-1);
    	backStrace(str1, n, m);
    
    	//for (int i = 0; i < n; ++i) {   //行
    	//	for (int j = 0; j < m; ++j) { //列
    	//		cout << path[i][j] << " ";
    	//	}
    	//	cout << endl;
    	//}
    
    	//释放dp数组内存
    	return 0;
    }

![在这里插入图片描述][8f164029f03f4594ae90609a212ef42a.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/478755dac831489e931d01ed0bc28c33.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/e68656aaea5f410d85be9df449fb15f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/3373d75b215e462fac4a0e5edb1d172a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/018f81e2408d49d092dd31049d7d259d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/98ccbbcd54cd497ea9db8578ba0e30a9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/b845c332079943278c956316bc1fa450.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/76a701ff5c8747c39b48fe3fdc514cf1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/75b18a7e5fc041cea716990ea0feaa3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/0c21f8057fb24c33a43e3e3cd2a0e233.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]: /images/20220829/bd099a2475c24afaa635514913e80cca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]: /images/20220829/7f9f4cea720c49ad99038a492fd06c9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]: /images/20220829/0168ac72b2214a789e80bf5b8e89362a.png
[8f164029f03f4594ae90609a212ef42a.png]: /images/20220829/2f874efa03e74165bf16ffc78ca8c783.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]: /images/20220829/2e9801b0dfec4191bdfbfe7b44843d20.png