p236练习题 动态规划 LCS 最长公共子序列 [编程题]Coincidence 习题P236 自己

//p236练习题 动态规划 LCS 最长公共子序列 [编程题]Coincidence 习题P236 自己
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 101;


int main(){
    char s1[MAXN];
    char s2[MAXN];
    int dp[MAXN][MAXN];

    gets(s1+1); // 从下标为1开始输入
    gets(s2+1);

    int n = strlen(s1 + 1); //由于读入时候下标从1开始，因此读取长度也从+1开始。
    int m = strlen(s2 + 1);

    for(int i=0;i<=n;++i){
        for(int j=0;j<=m;++j){
            if(i==0 || j==0){
                dp[i][j] = 0;
                continue;
            }
            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]);
        }

    }
    printf("%d",dp[n][m]);
    return 0;
}