HDU 1159 Common Subsequence DP 又一道水题

本文主要是介绍HDU 1159 Common Subsequence DP 又一道水题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题在做一遍的确是有了点收获。

这一次没有参考别人代码。自己写的, 不过不完全, 第一次交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;elsedp[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;
}
//不完全是自己写的。

这篇关于HDU 1159 Common Subsequence DP 又一道水题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---