用 total/end 两类状态区分总体方案和当前字符接在段内的方案，完成字符串分段 DP。
OJ: luogu
题目 ID: P2679
难度:提高+/省选-
标签:动态规划字符串计数DP
日期: 2026-06-22 23:15
题意
给定字符串 A、B 和整数 k。要从 A 中取出 k 个互不重叠的非空子串，按它们在 A 中出现的顺序拼接起来，要求结果等于 B。求方案数。
思路
朴素做法是枚举 k 个子串的位置，再判断拼接结果是否等于 B。
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：枚举 k 个不重叠子串并拼接，只适合很小的数据。
int n, m, need_k;
string a, b;
long long answer;
void dfs(int start_pos, int used, const string &built) {
if ((int)built.size() > m) {
return;
}
if (used == need_k) {
if (built == b) {
answer++;
}
return;
}
for (int l = start_pos; l <= n; l++) {
string next = built;
for (int r = l; r <= n; r++) {
next.push_back(a[r - 1]);
if ((int)next.size() > m) {
break;
}
dfs(r + 1, used + 1, next);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> need_k;
cin >> a >> b;
dfs(1, 0, "");
cout << answer % 1000000007 << '\n';
return 0;
}正式做法从左到右扫描 A。设：
total_dp[j][c]：处理过当前A前缀后，已经拼出B的前j位，并且用了c段的总方案数；end_dp[j][c]：当前A字符必须被选中，作为B[j]，并且它位于第c段内的方案数。
如果 A[i] == B[j]，那么选中 A[i] 有两种情况：
text
end_dp[j][c] = end_dp[j-1][c] + total_dp[j-1][c-1]end_dp[j-1][c]：延续上一段，当前字符接在已经选中的上一字符后面；total_dp[j-1][c-1]：新开一段，前面已经用c-1段拼出B的前j-1位。
得到新的 end_dp[j][c] 后，把它加入 total_dp[j][c]。如果 A[i] != B[j]，当前字符不能匹配 B[j]，对应的 end_dp[j][c] 要清零。
为了避免同一个 A[i] 被重复使用，j 和 c 都倒序枚举。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int MAXM = 205;
const int MAXK = 205;
int n, m, need_k;
string a, b;
int total_dp[MAXM][MAXK]; // total_dp[j][c]：处理过当前 A 前缀后，拼出 B 前 j 位且用了 c 段的方案数。
int end_dp[MAXM][MAXK]; // end_dp[j][c]：必须选当前 A 字符作为 B[j]，且它在第 c 段内的方案数。
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> need_k;
cin >> a >> b;
a = " " + a;
b = " " + b;
total_dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
for (int c = need_k; c >= 1; c--) {
if (a[i] == b[j]) {
// 继续上一段：上一位 B[j-1] 必须刚好由 A[i-1] 结尾。
// 新开一段：前 j-1 位可以在 A[1..i-1] 任意位置结束。
end_dp[j][c] = ((long long)end_dp[j - 1][c] + total_dp[j - 1][c - 1]) % MOD;
total_dp[j][c] += end_dp[j][c];
if (total_dp[j][c] >= MOD) {
total_dp[j][c] -= MOD;
}
} else {
end_dp[j][c] = 0;
}
}
}
}
cout << total_dp[m][need_k] << '\n';
return 0;
}复杂度
时间复杂度
空间复杂度
总结
这题的关键是区分“已经完成的总方案”和“当前字符必须被选中且接在某一段内的方案”。有了 end_dp，延续旧段和新开一段这两种来源就能被清楚地拆开。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
