abcfbc abfcab programming contest abcd mnp
4 2 0
当 i = 0 , j = 0 时 , dp[i][j] = 0
当 i , j > 0 ; xi = yi 时 ,dp[i][j] = dp[i-1][j-1] + 1
当 i , j > 0 ; xi != yi 时 ,dp[i][j] = max { dp[i][j-1] , dp[i-1][j] }
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
char str1[1005];
char str2[1005];
int dp[1005][1005];
int main()
{
while(scanf("%s %s",str1+1,str2+1)!=EOF)
{
memset(dp, 0, sizeof(dp));
int len1=strlen(str1+1);
int len2=strlen(str2+1);
for(int i=1; i<=len1; i++)
for(int j=1; j<=len2; j++)
{
if(str1[i]==str2[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;
}
HDU 1159：Common Subsequence（最长公共子序列）,布布扣,bubuko.com
HDU 1159：Common Subsequence（最长公共子序列）
原文：http://blog.csdn.net/u013487051/article/details/38272949