algorithm - 如何用DP解决 "Longest similar subsequence"

Question

我已经阅读了 LCS 问题的解决方案。但是现在有一个最长相似子序列问题:序列 C 是两个序列 A、B 的相似子序列当且仅当 C 是 A 的子序列并且我们最多可以替换 C 中的 K 个元素使得 C 是 B 的子序列.

例如，如果A = "ABCDE", B = "BCAFE", K = 1，则最长相似子序列为"BCDE"("BCDE是"ABCDE的子序列，我们可以用'D'代替使用 'A' 或 'F' 使其成为“BCAFE”的子序列)。

我的问题是我只是想出了一个递归的方法来解决它，但显然这很耗时，所以我想用DP代替。知道如何使用 DP 来解决这个问题吗？

我的递归方法是这样的:

LSS(i, j, k)
    if(i == 0 or j == 0)
        return 0
    if(A[i] == B[j])
        return LSS(i-1, j-1, k) + 1
    if(k > 0)
        return max(LSS(i-1, j-1, k-1) + 1, LSS(i-1, j, k), LSS(i, j-1, k))
    else
        return max(LSS(i-1, j, k), LSS(i, j-1, k))

Answer 1

DP 就是了解最优子问题，然后将其用于获得其他解决方案。没有所有这些细节，我们可以简单地使用自动出现的想法。

这里我们所做的只是一遍又一遍地计算相同的解决方案。这就是解决方案耗时更多的原因。您可以做的是记住解决方案。

所以在这种情况下，用 -1 初始化 sol。然后在获得 LSS(i,j,k) 的解之前，您可以检查 sol[i][j][k] 是否已经计算。如果是那么就使用它，否则解决解决方案并将其放入 sol。标准内存。