线性DP+滚动数组
参考题解
思路一(还一知半解)
题中明显提到了三个状态,所以我们可以轻松地写出DP数组的形式:$dp[i][j][p]$, 表示$A[1~i]$取$p$个子串, 首尾拼接后恰好和$B[1~j]$相等的总方案数。
该DP数组的转移方程需要考虑两种情况:
1. 不使用$A[i]$: 方案数=$dp[i-1][j][p]$
2. 使用$A[i]$:
2.1. $A[i]$新开一个串: 方案数=$dp[i-1][j-1][p-1]$
2.2. $A[i]$并入之前的串,
2.2.1. 若$A[i-1]$和$B[j-1]$不匹配, 方案数=$dp[i-1][j-1][p]$
2.2.2. 若$A[i-1]$和$B[j-1]$相匹配
2.2.2.1 若$A[i-2]$和$B[j-2]$继续匹配,方案数=$dp[i-2][j-2][p]$
…
总结来说就是: 对于$A[i]$纳入前面的子串的情况,必须找到这一整个子串。
$$f(i, j, k)=\\left\\{\\begin{array}{ll}f(i-1, j, k) & , A_{i} \\neq B_{j} \\\\f(i-1, j, k)+\\sum_{t=1}^{p+1} f(i-t, j-t, k-1) & , A_{i}=B_{j}\\end{array}\\right.$$
思路二
为了不需要找到可以接纳$A[i]$的整个子串,我们修改DP数组为$dp[i][j][k][0/1]$,最后1位表示是否使用当前的$A[i]$。
该DP数组的转移方程需要考虑两种情况:
1. 不用$A[i]$的方案数 = 不用$A[i-1]$ + 用$A[i-1]$
2. 用$A[i]$ = $A[i]$开新串(用$A[i-1]$+不用$A[i-1]$) + $A[i]$并入旧串(必须用$A[i-1]$)
那么转移方程变为:
$$\\begin{aligned}f_{i, j, p, 0} & =\\left\\{\\begin{array}{ll}f_{i-1, j, p, 0}+f_{i-1, j, p, 1} & a_{i}=b_{j} \\\\f_{i-1, j, p, 0}+f_{i-1, j, p, l} & a_{i} \\neq b_{j}\\end{array}\\right. \\\\f_{i, j, p, 1} & =\\left\\{\\begin{array}{ll}f_{i-1, j-1, p, 1}+f_{i-1, j-1, p-1,0}+f_{i-1, j-1, p-1,1} & a_{i}=b_{j} \\\\0 & a_{i} \\neq b_{j}\\end{array}\\right.\\end{aligned}$$
代码(方案二)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1005, M = 205, MOD = 1000000007;
using ll = long long;
//dp[i][j][p][0/1]: A[1~i]取p个子串, 首尾拼接后恰好和B[1~j]相等的总方案数, 0/1表示是否使用了A[i]
ll dp[2][M][M][2];
char a[N], b[M];
int main()
{
int n, m, k;
cin >> n >> m >> k;
scanf("%s%s", a+1, b+1);
dp[0][0][0][0] = dp[1][0][0][0] = 1; //dp[1][0][0][0]是必要的, 用于推导dp[2%2][1][1][1]
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
for(int p = 1; p <= k; p ++)
{
dp[i%2][j][p][0] = (dp[(i-1)%2][j][p][0] + dp[(i-1)%2][j][p][1]) % MOD; //不用a[i] = 不用a[i-1] + 用a[i-1]
if(a[i] == b[j])
{
////用a[i] = a[i]开新串(用a[i-1]+不用a[i-1]) + a[i]并入旧串(必须用a[i-1])
dp[i%2][j][p][1] = ((dp[(i-1)%2][j-1][p-1][0] + dp[(i-1)%2][j-1][p-1][1]) % MOD + dp[(i-1)%2][j-1][p][1]) % MOD;
}
else dp[i%2][j][p][1] = 0; //易漏: 因为此处是滚动数组
// printf("dp[%d][%d][%d][0]=%d dp[%d][%d][%d][1]=%d\n", i, j, p, dp[i%2][j][p][0], i, j, p, dp[i%2][j][p][1]);
}
}
}
cout << (dp[n%2][m][k][0] + dp[n%2][m][k][1]) % MOD << endl;
return 0;
}