algorithm - 子串部分数量受限的最长公共子序列

Question

最近我正在学习动态编程（DP），这个视频展示了建立 DP 表以获得最长的公共子序列（lcs）。

如果有另一个参数 m 限制子字符串部分的数量，这个表会是什么？例如，假设我们有 a="xxyzxyz" 和 b="xyz"，并且我们只允许将子字符串分成 2 个部分，所以 m=2。结果生成子字符串可以放在字符串中的最大组合数。

在这种情况下，我们有以下内容，

[x]xyx[yz]

x[x]yx[yz]

xxy[x][yz]

x[xy]x[z]

注意 [] 里面的字母被认为是 1 部分，所以我们有 2 个 [] 符合 m=2。所以在这种情况下，结果是 4。

我想知道如何建立我的 DP 表。能不能用一张 3-D 代替传统的 ab 2-D DP 表？我的猜测是 DP 方程是 lcs(a, b, m) ？

谢谢！

标签： algorithmdynamic-programmingcomputer-science