这题在做一遍的确是有了点收获。
这一次没有参考别人代码。自己写的, 不过不完全, 第一次交WA了。
第二次才A掉。
状态方程：如果str1[i] == str2[j] 则dp[i][j] = dp[i-1][j-1] + 1
如果str1[i] != str2[j] 则dp[i][j] = max(dp[i-1][j], dp[i][j-1])
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int dp[1000][1000];
int max1 (int a, int b)
{
return a > b ? a : b;
}
int main()
{
int i, j, m, n;
char str1[1000], str2[1000];
while (scanf("%s %s", str1, str2) != EOF)
{
memset(dp, 0, sizeof(dp));
m = strlen(str1);
n = strlen(str2);
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
{
//比较串1 与 串2字符是否相等
//比较前一字符 so, i, j 初始化为1
//dp[i][j] 记录的是str1的i-1个字符状态和str2的j-1个字符状态
if (str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max1(dp[i-1][j], dp[i][j-1]);
//printf("i = %d j = %d dp[i][j] = %d\n", i, j, dp[i][j]);
}
printf("%d\n", dp[m][n]);
}
return 0;
}
//不完全是自己写的。