DPを使用して「最長類似サブシーケンス」を解決する方法

Question

LCSの問題の解決策を読みました。しかし、現在では最長類似サブシーケンス問題があります。シーケンスCは、CがAのサブシーケンスであり、CがBのサブシーケンスであるようにC内のK個の要素を置き換えることができる場合に限り、2つのシーケンスA、Bの類似したサブシーケンスです例えば、A = "ABCDE"、B = "BCAFE"、K = 1の場合、最も長い類似サブシーケンスは "BCDE"（ "BCDEは" ABCDE "のサブシーケンスであり、 D 'を "A"または "F"で "BCAFE"のサブシーケンスにする）。

私の問題は、これを解決するための再帰的な方法しか考え出されていないことですが、明らかにこれには時間がかかりますDPを使用してこの問題を解決する方法はありますか？

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は、すべて最適なサブ問題を理解していて、それを他の解決策を得るために使用します。すべての詳細がなければ、私たちは単に自動的に来るアイデアを使用することができます。

ここでは、単純に同じソリューションを何度も繰り返し計算しています。だからこそ、このソリューションははるかに時間がかかります。あなたができることは、解決策をメモすることです。

この場合、solを-1で初期化します。 LSS（i、j、k）の解を得る前に、sol[i][j][k]がすでに計算されているかどうかを確認することができます。それがそうでなければそれを使用しているならば、それを解決してsolに入れてください。スタンダードメモ。