私は動的プログラミングを独学しようとしていますが、MIT からこの問題に遭遇しました。
4 行 n 列のチェッカーボードが与えられ、各正方形に整数が書かれています。また、2n 個の小石のセットが与えられており、これらの一部またはすべてをチェッカーボードに配置して (各小石は正確に 1 つの正方形に配置できます)、これらの正方形でカバーされる正方形の整数の合計を最大化します。小石。1 つの制約があります。小石の配置が正当であるためには、小石の 2 つを水平または垂直に隣接する正方形に置くことはできません (対角線の隣接は問題ありません)。
(a) 任意の列で発生する可能性のある正当なパターンの数を決定し (孤立して、隣接する列の小石を無視して)、これらのパターンを説明します。正当な配置を形成するために隣接する列に配置できる場合、2 つのパターンを互換性があると呼びます。最初の k 列 1 k n からなる部分問題を考えてみましょう。各サブ問題には、最後の列で発生するパターンであるタイプを割り当てることができます。
(b) 互換性と型の概念を使用して、最適な配置を計算するための O(n) 時間の動的計画法アルゴリズムを与えてください。
さて、パート a について: 8 つの可能な解決策があります。
パート b については、確信が持てませんが、これが私が向かっているところです: サブ問題に分割します。n に i を仮定します。1. 列 i がパターン タイプ j を持つように、列 0,...,i をペブリングすることにより、Cj[i] を最適な値に定義します。2. パターン タイプごとに n 要素の 8 つの個別の配列を作成します。
ここからどこへ行けばいいのかわからない。この問題の解決策がオンラインにあることは認識していますが、解決策はあまり明確ではないようです。