矩陣中的子和元素的動態編程

給定一個4行棋盤和n列。在每個單元格中都有一個整數。鑑於2n光盤，其中的一部分，或者他們都可以放在板上的不同單元，所以總和是最大的。唯一的限制是2個碟片不能相互垂直或水平相鄰。如何使用DP在O(n)上將最佳光盤組合放置在電路板上？矩陣中的子和元素的動態編程

來源

2015-05-19 itorra

所以我已經說過，每列有7種可能性模式（不放置光盤不是一個選項導致問題說部分）。我創建了一個矩陣M，如果我可以在列i + 1旁邊放置一個列爲c（可以是0到6）的列，將輸出T或F.所以我想安排n個優先級隊列大小爲7，隊列中的每個元素都是一對分類和來自該分類的數字的總和，在這裏我卡住了 – itorra

爲什麼要使用優先級隊列？試着想想你會如何將其作爲一個DP來制定。您希望找到描述如何構建解決方案的重現。從簡單開始：如果對我們可以在哪裏放置光盤的位置沒有限制，您將如何制定DP？ –

所以我想到sum（n）= sum（n-1）+ max {pik：k從0到可能模式的數量}。（p - 當前列）問題是每當我需要插入條件時我不能回頭改變整個子問題 – itorra

1，我們不可能使用多於2 * n的磁盤，因爲任何列最多可以包含2個磁盤。

比方說，d [i] [掩碼] - 用磁盤填充從1到i的列後獲得的最大數量，以便最後一列填充爲掩碼（掩碼可以是0000，0001，0010，0100，0101，1000 ，1001或1010，其中1表示磁盤被放置，0表示它不是）

因此，d [i] [mask1] =（d [i-1] [mask2]的最大值+第2列），其中掩碼2可以是與掩碼1不抵觸的任何掩碼1

編輯1：您不需要更改任何內容。當你在某個面具上的第i步時，它僅取決於i-1的面具的答案。而你已經擁有了所有這些。你只是嘗試從當前有效的d [i] [mask]中更新。正如我已經說過的那樣d [i] [mask] - 存儲可以從1到i填充列的最大值，最佳地使最後一列具有此掩碼形式的磁盤（在我之前沒有掩碼因爲它們不會影響下一列）

來源

2015-05-20 04:19:20 Herokiller

假設在第i列應用mask1得到的數字非常大，而mask1與mask2矛盾，我在哪裏檢查如何改變子問題中的所有內容，以便我可以在d [i] [mask1 ]？ – itorra

@itorra更新了我的答案。也許如果你有一個例子，我可以解釋一下 – Herokiller

矩陣中的子和元素的動態編程

回答

相關問題