题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=1159
分析:用一个二维的表格来记录以前的最优值,递推关系式为:
当前字符str1[i] == str2[j],dp[i][j] = dp[i -1][j-1] + 1;
否则,dp[i][j] = max(dp[i -1][j] ,dp[i][j -1]);
参考代码:
#include<stdio.h> #include<string.h> #define M 2010 char str1[M]; char str2[M]; int dp[M][M]; inline int max(const int a, const int b) { return a > b ? a : b; } void main() { int nLen1, nLen2; int i,j; int nMax; while(scanf("%s %s",&str1,&str2) != EOF) { nLen1 = strlen(str1); nLen2 = strlen(str2); memset(dp,0,sizeof(dp)); nMax = 0; for(i = 1; i <= nLen1; ++i) { for(j = 1; j <= nLen2; ++j) { if(str1[i - 1] == str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } nMax = max(nMax, dp[i][j]); } } printf("%d\n",nMax); } }