首页 > 技术文章 > Poj 1458 Common Subsequence

lusiqi 2020-02-26 22:31 原文

 

 代码:

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn = 1005;
int dp[maxn][maxn];
int main(){
    char s1[maxn],s2[maxn];
    while(cin>>s1+1>>s2+1){
        int len1 = strlen(s1+1);
        int len2 = strlen(s2+1);
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++)
                dp[i][j] = 0;
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;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[len1][len2]<<endl;
    }
    return 0;
}

 

推荐阅读