ダイナミックプログラミング - 最大値

Question

Question I need Help with: CHECK HERE

を見つける3 sequences.andでは、この問題といくつかの助けが必要。入力として

トリートBと逆方向に行くので、次にB.に合致するものを見つけるためにBの最後の値を取り、後ろからAを通じて見て：私は今のところ思い付いた

ソリューションですBの最初の値をとり、正面からAを見て、一致する最初の値を見つけます。両方の値を保存します。

次に、2つの上限と下限の間の比較を行って、最初のステップで見つかった値よりも大きな値を見つけます。要件を満たすようにします。 B =（x、y）の問題で与えられた例では、XはYの前に来なければならないので、最後のYの後に来るXが最大であっても、それを選択することはできません。

私はそれがO（MxN）時間に実行されると信じていますが、私は非常に不確かであり、なぜ私はあなたに頼んでいるのですか。

お時間をいただきありがとうございました。皆さんからお手伝いできます。

Answer 1

解決策は、ダイナミックプログラミングのようにまったく発音しません。

問題は、基本的には共通のサブシーケンスは、AとBの間であり、合計はPから最大和longest common subsequenceを見つけるために尋ねます。

問題に対してLCSソリューションを適用することは可能です。あなたはLCS行列が構築されれば、実際のLCSを取得するには、古典的なバックトラッキングアルゴリズムを検討し、Pから金額を選択する必要がありますので：

backtrack(LCS, A, B, i, j): 
    if i == 0 or j == 0 
     return "" 

    if A[i] == B[j]: 
     return backtrack(LCS, A, B, i-1, j-1) + A[i] 
    else if LCS[i-1, j] > LCS[i, j-1]: 
     return backtrack(LCS, A, B, i-1, j) 
    return backtrack(LCS, A, B, i, j-1) 

今、あなたは最高の合計を見つける必要がある：

backtrack(LCS, A, B, i, j, s=0): 
    if i == 0 or j == 0 
     return s 

    if A[i] == B[j]: 
     return backtrack(LCS, A, B, i-1, j-1, s + P[i]) 
    else if LCS[i-1, j] > LCS[i, j-1]: 
     return backtrack(LCS, A, B, i-1, j, s) 
    else if LCS[i-1, j] < LCS[i, j-1]: 
     return backtrack(LCS, A, B, i, j-1, s) 
    else: 
     return max(backtrack(LCS, A, B, i-1, j, s), 
        backtrack(LCS, A, B, i, j-1, s)) 

あなたがかもしれません効率的な実装のためにメモを適用する必要があります。また、LCS行列の横に（またはその代わりに）合計行列を計算することも可能でなければなりません。