动态规划---最大公共子序列（不连续）

蔚落 2023-06-25 02:24 12阅读 0赞

### 比如：“programming” 和 “contest”，可以找到的最长的公共子序列（不连续）是"on",所以最大公共子序列长度（不连续）为 2 ###

### 1、最开始的思路是递归 ###

我们可以看到右边那个 代码表达式，很直观的说明了如何返回 LCS（最大公共子序列长度）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]  
但众所周知，递归是很耗时的，所以我们可以试着**改进**

### 2、将递归转换成 DP（动态规划） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 1]  
右边的代码表达式即由递归转换而来的 DP（动态规划），我们还可以通过表达式推导出 LCS 是什么，如左边的表，最后推导出是 one

**但是注意：** 我们要先对表格边界进行初始化，因为两个子序列之间，若其中一方没有字母，则公共部分为 0

**代码：**

#include <iostream>
    #include <cstring>
    #define _for(a,b,c) for(int a=b;a<c;a++)
    #define N 256
    using namespace std;
    char s1[N],s2[N];
    int maxLen[N][N];
    int main()
    { 
    	cin >> s1 >> s2;
    	int len1 = strlen(s1);
    	int len2 = strlen(s2);
    	_for(i,0,len1+1) maxLen[i][0] = 0;
    	_for(j,0,len2+1) maxLen[0][j] = 0;
    	_for(i,1,len1+1)
    		_for(j,1,len2+1)
    		{ 
    			if(s1[i-1] == s2[j-1]) maxLen[i][j] = maxLen[i-1][j-1] + 1;
    			else maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]);
    		}
    	cout << maxLen[len1][len2] << endl;
    	return 0;
    }

**提醒：**  
在表格（0，0）处与两条边界处都初始化为 0，故计算 LCS的 for 循环要从 1 开始 并在原序列长度处停止

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191225125658960.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191225131404194.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70