首页 > 代码库 > LCS的数量
LCS的数量
题意:
给出两个字符串,A,B,求A,B的lcs的数量。
题解:
在LCS的时候同时计算方案QAQ,可是傻逼的我不会,不会,不会。。。。。。
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int mod = 1e9 + 7; const int N = 1e3 + 7; int dp[N][N], sum[N][N]; char ch1[N], ch2[N]; int main () { scanf ("%s%s", ch1 + 1, ch2 + 1); int n = strlen (ch1 + 1); int m = strlen (ch2 + 1); for (int i = 0; i <= n; ++i) sum[i][0] = 1; for (int j = 0; j <= m; j++) sum[0][j] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (dp[i][j] < dp[i - 1][j]) { dp[i][j] = dp[i - 1][j]; sum[i][j] = sum[i - 1][j]; } else if (dp[i][j] == dp[i - 1][j]) { sum[i][j] = (sum[i][j] + sum[i - 1][j]) % mod; } if (dp[i][j] < dp[i][j - 1]) { dp[i][j] = dp[i][j - 1]; sum[i][j] = sum[i][j - 1]; } else if (dp[i][j] == dp[i][j - 1]) { sum[i][j] = (sum[i][j] + sum[i][j - 1]) % mod; } if (ch1[i] == ch2[j]) { if (dp[i][j] < dp[i - 1][j - 1] + 1) { dp[i][j] = dp[i - 1][j - 1] + 1; sum[i][j] = sum[i - 1][j - 1]; } else if (dp[i][j] == dp[i - 1][j - 1] + 1) { sum[i][j] = (sum[i][j] + sum[i - 1][j - 1]) % mod; } } } } printf("%d\n", sum[n][m]); return 0; }
总结:
一个基础的DP,我竟然不会QAQ,我真为“志几”感到捉急...
LCS的数量
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。