POJ1458 HDU1159 Common Subsequence（最长公共子序列 DP）

题目链接

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
char s1[1005];
char s2[1005];
int dp[1005][1005];
int main(){
    //freopen("a.txt", "r", stdin);
    while(~scanf("%s %s", s1+1, s2+1)){
        memset(dp, 0, sizeof(dp));
        s1[0] = ' ';s2[0] = ' ';
        int l1 = strlen(s1)-1;
        int l2 = strlen(s2)-1;

        for(int i = 1; i <= l1; i++){
            for(int j = 1; j <= l2; 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[l1][l2] << endl;
    }
    return 0;
}