解题思路:
假设两个字符串分别为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 人评分
printf基础练习2 (C语言代码)浏览:618 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:558 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:514 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:689 |
IP判断 (C语言代码)浏览:539 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:403 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:1200 |
C语言训练-最大数问题 (C语言代码)浏览:591 |
【偶数求和】 (C语言代码)浏览:441 |
1025题 初学者,求帮忙看下,不知道哪错了浏览:316 |