题解 | #最长公共子序列(一)#

设dp[i][j]表示

1~i的s1子串和1~j的s2子串的最长公共子序列的最大长度

思想：从哪里来

如果s1[i]==s2[j]了，那这个f[i][j] = max(f[i][j], f[i-1][j-1]+1)

如果s1[i]!=s2[j]

f[i][j] <-- max( f[i-1][j], f[i][j-1], f[i][j])

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int dp[N][N];  //长度为i的s1子串和长度为j的s2子串 的最长公共子序列
int main() {

    int n,m;
    scanf("%d%d",&n,&m);
    char s1[N];
    char s2[N];
    scanf("%s",(s1+1));
    scanf("%s",(s2+1));

    for(int i = 1;i<=n;i++)
    {
        for(int j = 1; j<=m;j++){
            dp[i][j] = max(dp[i][j], max(dp[i-1][j], dp[i][j-1]));
            if(s2[j]==s1[i]){
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
            }

        }
    }
    printf("%d",dp[n][m]);
    return 0;                          
}
// 64 位输出请用 printf("%lld")