ダイナミックプログラミングのサブ問題をどのように設計/単語化するのですか？

Question

私はボトムアップの動的プログラミング方法を試しています。私はそれにいくつかの問題があります。

以前に計算された値を1Dまたは2D配列に格納し、必要に応じてそれらを参照することによって、必要な解決策に到達することを学びました。問題は、私の配列に格納されている値を使ってバックトラックすることができないことです。

たとえば、問題が古典的な「Longest Subsequence」問題である場合、最も長いサブシーケンスの値に到達できますが、格納された値をバックトラックして、どの文字/数字がサブシーケンス。

私は多くの大学のコースのチュートリアルやYouTubeのチュートリアルを終えましたが、どのようにして人がサブ問題を正しく語りかけることができるか説明していないようです。

誰でもサブ問題を工夫し、配列の値を維持してバックトラックを可能にし、簡単にする方法についてのヒントはありますか？

Answer 1

単純な解決策は、最初の配列と同じ次元の2番目の配列を保持し、それをindex配列と呼び、それを使用して選択に寄与した要素の位置を追跡することです。 2Dの例で

だから：
うAは
値A[x,y]は次にI[x,y]=(x0,y0)、A[x0,y0]によって決定された場合Iインデックスアレイを

をとする標準的な動的プログラミング・アレイです。

A[i,j]からバックトラックしようとすると、I[i,j]にアクセスしてバックトラックチェーンの次の要素を見つけます。

アレイのデフォルト値はIなので、チェーンの終わりに達した時点を知ることができます。