首页 > 代码库 > 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的数量