dp最长公共子序列

给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。

输入格式
第一行包含两个整数N和M。

第二行包含一个长度为N的字符串，表示字符串A。

第三行包含一个长度为M的字符串，表示字符串B。

字符串均由小写字母构成。

输出格式
输出一个整数，表示最大长度。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int dp[1010][1010];
char s1[1010];
char s2[1010];
int main(){
    //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //f[i][j]指的是长度为i的A串和长度为j的B串的最长公共子序列长度
    //如果两个字符相等，就可以直接转移到f[i-1][j-1]，不相等的话，两个字符一定有一个可以抛弃，可以对f[i-1][j],f[i][j-1]两种状态取max来转移。
    int n,m;
    cin>>n>>m;
    cin>>s1+1>>s2+1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i] == s2[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;
} 

dp最长公共子序列

原文：https://www.cnblogs.com/jccodingforfun01/p/14157543.html