动态规划求解选取指定数量不重叠子串组成目标串的方法数

状态定义 #

我们用三维状态dp[i][j][k]表示：使用原字符串前i个字符，恰好匹配目标字符串前j个字符，且已经选取了k个非重叠子串时的总方案数。该定义可以覆盖所有子问题场景。

重叠子问题说明 #

和背包问题的子问题复用逻辑一致，本问题的重叠子问题体现在：不同上层决策路径会重复调用同一个子状态的结果。比如计算「原串前5个字符匹配目标前3个字符、用了2个子串」的方案时，会复用「原串前3个字符匹配目标前2个字符、用了1个子串」的结果，不需要重复计算。

Base Case 设定 #

• 对所有i≥0，dp[i][0][0] = 1：当目标字符串匹配长度为0、选取子串数量为0时，只有1种方案（不选任何字符）
• 其余初始状态均为0，可额外做剪枝：当k>j时直接返回0，因为每个子串至少贡献1个匹配字符，k个子串最少匹配k个字符，不可能出现用k个子串匹配少于k个字符的情况

状态转移逻辑 #

状态转移分两种决策分支：

1. 不选取原串第i个字符：直接继承前i-1个字符的计算结果，即 dp[i][j][k] += dp[i-1][j][k]
2. 选取原串第i个字符参与匹配，要求满足origString[i-1] == toMatch[j-1]（字符串索引从0开始，状态索引从1开始），再分两种子情况：
   • 当前字符是第k个子串的首字符：累加dp[i-1][j-1][k-1]的结果
   • 当前字符是第k个子串的后续字符：累加dp[i-1][j-1][k]的结果

边界优化 #

如果maxNum > len(toMatch)，直接返回0，最多只能选len(toMatch)个单字符子串匹配目标，超过这个数量没有合法方案。
按以上逻辑计算示例场景：origString = "ppkpke"、toMatch = "ppke"、maxNum=2时，最终dp[6][4][2]的结果就是4，和示例给出的结果一致。

内容的提问来源于stack exchange，提问作者TabPo