用動態編程玩弄棋盤格

Question

我想教自己動態編程，並從麻省理工學院遇到這個問題。

我們給出了一個有4行n列的棋盤，而 有一個寫在每個正方形中的整數。我們還給了一組2n鵝卵石，並且我們想要 將這些中的一些或全部放置在棋盤上（每個卵石可以放置在正好一個正方形上），以便最大化正方形中整數的總和由鵝卵石覆蓋。有一個約束：對於放置鵝卵石是合法的，它們中的任何一個都不能水平放置，或者垂直相鄰的方格（對角線鄰接是正確的）。 （a）確定任何列中可能出現的合法模式的數量（單獨，忽略鄰近列中的卵石），並描述這些模式。 如果兩個圖案可以放在相鄰列上以形成合法佈局，則調用兩個圖案兼容。讓我們考慮由第k個列1 k n組成的子問題。每個子問題 可以分配一個類型，這是最後一列中出現的模式。 （b）使用兼容性和類型的概念，給出一個O（n）時間動態規劃算法來計算最佳位置。

好的，所以對於第一部分：有8種可能的解決方案。

對於b部分，我不確定，但這是我的目標： 分爲子問題。假設我在n。 1.通過對列0，...，i進行鵝卵石化，將Cj [i]定義爲最優值，使得列i具有模式類型j。 2.爲每種模式類型創建8個獨立的n個元素數組。

我不確定該從哪裏出發。我意識到網上有這個問題的解決方案，但解決方案似乎不是很清楚。

Answer 1

你在正確的軌道上。當你檢查每一個新的專欄時，你將最終計算出所有可能的最佳分數。

比方說，你建立你的兼容性列表（二維數組），並把它稱爲大號_我 [Y]，使得每個模式我有一個或多個兼容模式大號_我 [Y ]。

現在，您檢查列j。首先，您計算每個模式的分列得分i。叫它S _j [i]。對於每個模式我和兼容 圖案X = L _我 [Y]，需要最大化總得分Ç_Ĵ使得Ç_Ĵ [X] = C _{J- 1} [i] + S _j [x]。這是一個簡單的數組測試和更新（如果更大）。

此外，您還可以存儲導致每個樂譜的鵝卵石花紋。當更新Ç_Ĵ [X]（即您增加從它的當前值的分值），則請記住，導致更新爲P _Ĵ的初始和後續圖案[X] = I。這說「模式x給出了最好的結果，給定前面的模式我」。

當你完成所有的工作，只要找到模式我最好的得分Ç_ň [I]。然後，您可以使用P _j回收來自導致該結果的每列的鵝卵石樣式。