ダイナミックプログラミングによるチェッカーボードのフレーブ

Question

ダイナミックプログラミングを教えようとしていて、MITからこの問題に遭遇しました。

4行n列のチェッカーボードが与えられ、 の整数は各四角に書かれています。我々はまた、2n小石のセットを与えられており、我々は チェッカーボード上にこれらのいくつかまたは全てを置くことを望む（それぞれの小石は正確に1つの正方形に置くことができる） そのような四角形の整数の合計を最大にする。小石で覆われています。 という制約が1つあります。小石を正当に配置するためには、2つを水平に配置することはできません。または、 は垂直に隣接する正方形にすることができます（対角隣接は大丈夫です）。

（a）任意の列に（孤立して、隣接する列の小石を無視して）、そのパターンを記述する法的パターンの数を決定します。 正式な配置を形成するために隣接する列に配置できる場合は、2つのパターンに互換性があります。 最初のk個の列1 k nからなる部分問題を考えてみましょう。各サブ問題は にタイプを割り当てることができます。これは最後の列で発生するパターンです。

（b）互換性とタイプの概念を使用して、最適な配置を計算するためのO（n）時間動的プログラミングアルゴリズムを提供します。

[OK]をクリックすると、パートa：8つの解決策があります。

パートbについてはわかりませんが、これは私がここに向いているところです： サブ問題への対処。 nで私を仮定する。 1.カラムiがパターンタイプjを持つように、カラム0、...、iをペブルすることによってCj [i]を最適値に定義します。 2.パターンタイプごとに8つのn要素の配列を作成します。

ここからどこに行くのかわかりません。私は、オンラインでこの問題の解決策があることを認識していますが、解決策は私にはあまり明確ではないようです。

Answer 1

あなたは正しい道を歩いています。それぞれの新しい列を調べると、その時点までに可能なすべてのベストスコアが計算されます。

各パターンのために私は1つまたは複数の互換性のパターンL _があるように[Y]私は [Yさんは、私はあなたは、互換性リスト（2次元配列）を構築し、L _{それを呼ばれるとしましょう]}。

ここで、列jを調べます。まず、各パターンの列の分離スコアを計算します。i。 S _j [i]としてください。各パターンについてIと互換 パターンX = L _I [Y]、あなたは合計スコアCを最大化するために必要 _JようC _J [X] = C _{J- 1} [i] + S _j [x]である。これは、単純な配列テストと更新（大きい場合）です。

さらに、各スコアにつながったペブルパターンを保存します。もしCを更新 _J [X]（すなわちあなたは、その現在の値から、そのスコアを増加させる）、次いでP _Jとして更新を引き起こし、初期およびその後のパターンを覚えている[X] = I。つまり、「xのパターンは、先のパターンi」と与えられていると、最良の結果が得られました。最高得点C _Nと

あなたがすべて完了している、ちょうどパターンを見つける私は [i]を。 P _jを使用してバックトラックして、この結果につながった各列からペブルパターンを回復することができます。