220. 最长公共子序列问题（挑战程序设计竞赛）

地址 https://www.papamelon.com/problem/220

给定两个字符串s_1s_2...s_n和t_1t_2...t_n.求出这两个字符串的最长公共子序列的长度。

输入
输入第一行有两个整数m和n,分别表示字符串s和t的长度,输入第二行和第三行分别表示字符串s和t.
1≤n,m≤1000.
输出
对于每行输入，输出一行，包含一个整数，表示这两个字符串![](/i/l/?n=23&i=blog/332907/202301/332907-20230102160551013-1069208185.png)
的最长公共子序列的长度.
样例 1
输入
4 4
abcd
becd
输出
3

题解
动态规划 时间复杂度O(nm)

假设dp[i][j] 表示 S字符串第i个和T字符串第j个的位置上 能达到的最长公共子序列

那么

#include <iostream>
#include <string>

using namespace std;
const int N = 1010;
int dp[N][N];
int n,m;
string a,b;


int main(){
    cin>>n>>m;
    cin >>a>>b;
    a.insert(a.begin(),'#');
    b.insert(b.begin(),'@');

    for(int i=1;i<=n;i++){
        for(int j= 1;j<=m;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[n][m]<<endl;

    return 0;
}

我的视频题解空间