如何使用DP来解决“最长的相似子序列”

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来解决这个问题？

我的rec ursion方法是这样的：

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。标准备忘录。