带子串段数限制的最长公共子序列（LCS）DP表构建问题

维度设计 #

你的判断是对的，该场景需要在传统二维LCS的基础上升级为三维DP表，状态结构和你提到的lcs(a, b, m)形式完全对应，新增的第三维度用来维护当前使用的公共子串段数。

状态定义 #

我们定义dp[i][j][k]为：使用字符串a的前i个字符、字符串b的前j个字符，恰好拼接出k段连续公共子串的方案总数。
如果需要统计最多m段的总方案数，最后对k从1到m的结果求和即可。

边界条件 #

• dp[0][0][0] = 1：两个空串匹配0段，仅存在1种方案
• 对任意i，dp[i][0][0] = 1：用a的任意前缀匹配空串，不需要使用段，仅存在1种方案
• 其余状态初始值为0

状态转移逻辑 #

分两种情况处理：

当前字符不匹配 #

当a[i-1] != b[j-1]（字符串下标从0开始）时，无法用a的第i位参与匹配，直接继承前序结果即可：

dp[i][j][k] += dp[i-1][j][k]

当前字符匹配 #

当a[i-1] == b[j-1]时，有两种转移选择：

• 将当前匹配字符接在已有最后一段的末尾，不新增段数，从dp[i-1][j-1][k]转移
• 将当前匹配字符作为新段的首个字符，段数加1，从所有dp[x][j-1][k-1]（x < i）的前缀和转移
  如果不想额外做前缀和优化，也可以新增辅助状态g[i][j][k]表示a前i位、b前j位、最多k段的所有方案总和，直接用g[i-1][j-1][k-1]作为新段的转移来源，代码实现会更简单。

示例验证 #

你给出的测试用例a="xxyzxyz"、b="xyz"、m=2，按照上述DP规则计算后，求和dp[7][3][1] + dp[7][3][2]得到的结果为4，和你给出的示例结果完全一致。

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