我试图自学动态编程，并从MIT遇到了这个问题。
我们给了一个棋盘，它有4行n列，并且
在每个方块中都有一个整数。我们还得到了一组2n个卵石，我们想要
将其中的一些或全部放在棋盘上(每个小卵石都可以恰好放在一个正方形上)
以便最大化卵石覆盖的正方形中整数的总和。有
一个约束:为了使小卵石的放置合法，它们中的任何两个都不能水平放置或
垂直相邻的正方形(对角线邻接即可)。
(a)确定在任何列中可能出现的法律模式的数量(孤立地，忽略
(相邻列中的小卵石)并描述这些模式。
如果可以将两个模式放在相邻列上以形成合法位置，则称这两个模式兼容。
让我们考虑由第一个k列1 k n组成的子问题。每个子问题可以
被分配一种类型，这是在最后一列中发生的模式。
(b)使用兼容性和类型的概念，给出O(n)时间动态规划算法，用于计算最佳位置。
好的，所以对于a部分:有8种可能的解决方案。
对于b部分，我不确定，但这就是我要去的地方:
分解为子问题。假设我在n中。
1.通过遍历列0，...，i，将Cj [i]定义为最佳值，以使列i具有模式类型j。
2.为每种模式类型创建8个n元素的单独数组。
我不确定从这里要去哪里。我意识到可以在线解决此问题，但是解决方案对我而言似乎并不十分清楚。
最佳答案
您走在正确的轨道上。在检查每个新列时，最终将计算出该点之前所有可能的最佳成绩。
假设您建立了兼容性列表(一个2D数组)并将其命名为 Li [y] ，这样，对于每种模式和，就有一个或多个兼容模式 Li [y] 。
现在，您检查 j 列。首先，为每种模式 i 计算该列的孤立分数。称之为 Sj [i] 。对于每种模式我并兼容
模式 x = Li [y] ，您需要使总得分 Cj 最大化，以便 Cj [x] = Cj-1 [i] + Sj [x] 。这是一个简单的数组测试和更新(如果更大)。
此外，您还存储了导致每个得分的令人讨厌的模式。当您更新 Cj [x] (即，从其当前值增加分数)时，请记住导致更新的初始模式和后续模式为 Pj [x] = i 。也就是说，“鉴于前面的和模式， x 模式给出了最佳结果”。
完成后，只需找到得分最高的模式 i 即可 Cn [i] 。然后，您可以使用 Pj 进行回溯，以从导致此结果的每一列中恢复磨擦模式。