动态规划（4）：最长公共子序列长度

系统管理员 2022-02-05 01:59 83阅读 0赞

## 题目 ##

给定两个字符串（或数字序列） A 和B, 求二个字符串，使得这个字符串是A 和B 的最  
长公共部分的长度（子序列可以不连续）

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

## 样例 ##

输入  
sadstory  
adminsorry  
输出  
6

## 题解 ##

**思路**:

如果两个串的最后结尾的字符相同,其最长公共子序列长度=分别去掉结尾字符剩下的部分的最长公共子序列长度+1;  
不相同,则转化为相同:在其中任意一个串上补与另一个串结尾字符相等的字符,然后转化成上面的情况,再进去因为补上字符多增加的长度1;

**最优子结构**(举例)：比如求sadstory 和adminsorry的最长公共子序列一定包含sadstor和adminsorr这两个串的最长公共子序列

**重复子问题**:比如求sadstory 和adminsorry的最长公共子序列和求sadstor和adminsorr这两个串的最长公共子序列,一定都要用到求sadsto和adminsor的最长公共子序列

**状态转移公式**:

dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+1, A\[i\]=B\[j\]  
dp\[i\]\[j\]=max(dp\[i-1\]\[j\], dp\[i\]\[j-1\]), A\[i\]!=B\[i\]

**时间复杂度** O(mn)

## C++代码 ##

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include"algorithm"
    
    using namespace std;
    #define N 100
    int main()
    { 
    	char A[N],B[N];
    	int dp[N][N];
    	gets(A+1);
    	gets(B+1);
    	int lenA=strlen(A+1);
    	int lenB=strlen(B+1);
    	for(int i=0;i<=lenA;i++)
    			dp[i][0]=0;
    	for(int j=0;j<=lenB;j++)
    			dp[0][j]=0;
    	
    	for(int i=1;i<=lenA;i++)
            for(int j=1;j<=lenB;j++)
    	        { 
    	        	if(A[i]==B[j])
         				 dp[i][j]=dp[i-1][j-1]+1;
    	        	else
    					 dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    			}
    	cout<<dp[lenA][lenB];
    }

[20190504132209199.png]: /images/20220205/cc756886f6bf4e29a166ed3d739b8d14.png