解题思路:
假设两个字符串分别为s1, s2
dp[i, j]表示s1以s1[i - 1]结尾和s2以s2[i - 1]结尾结尾时的最长上升子序列的长度。
注意事项:
dp[len1][0] = dp[0][len2] = 0;
参考代码:
#include <stdio.h> #include <string.h> #define max(a, b) a > b ? a : b char s1[1005], s2[1005]; int dp[1005][1005]; int main() { scanf("%s%s", s1, s2); int len1 = strlen(s1), len2 = strlen(s2); for (int i = 1; i <= len1; ++i) { for (int j = 1; j <= len2; ++j) { if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } } printf("%d\n", dp[len1][len2]); return 0; }
0.0分
1 人评分