用动态程序设计棋盘

Question

我想自学动态编程，却在麻省理工学院遇到了这个问题。

我们得到了一个有4行n列的棋盘，并且 在每个正方形中都有一个整数。我们还得到了一组2n卵石，我们想 在棋盘上放一些或所有这些（每个小石子可以正好放在一个正方形上） 使被卵石覆盖的正方形中的整数和最大化。有 一个限制条件是：要使鹅卵石的放置合法，它们中的任何两个都不能水平放置或 垂直邻接正方形（对角线邻接可以）。

（a）确定任何列中可能出现的法律模式的数量（孤立地，忽略 并描述了这些模式。 如果两个模式可以放置在相邻的列上，则调用它们以形成合法的放置。 让我们考虑由rst k列1k n组成的子问题 分配一个类型，这是最后一列中出现的模式。

（b）利用相容性和类型的概念，给出了计算最优布局的O（n）-时间动态规划算法。

好的，那么a部分：有8种可能的解决方案。

对于b部分，我不确定，但这是我的出发点： 分成子问题。假设我在n。 一。将Cj[i]定义为通过将列0，…，i设置为最佳值，从而使列i具有模式类型j。 2。为每种模式类型创建8个n个元素的独立数组。

我不知道从这里到哪里去。我意识到网上有解决这个问题的办法，但我觉得解决办法不是很清楚。

Answer 1

你在正确的轨道上。当你检查每一个新的专栏，你将计算所有可能的最佳分数，直到那一点。

假设您构建了兼容列表（一个2D数组），并将其命名为L_i[y]这样，对于每个模式i都有一个或多个兼容模式L_i[y]。

现在，检查列j。首先，计算每个模式下该列的独立分数。称之为S_j[i]。对于每个模式 模式x=L_i[y]，您需要最大化总分C_j以便C_j[x]=C_j-1[i]+S_j[x]。这是一个简单的数组测试和更新（如果更大的话）。

此外，还可以存储导致每个分数的鹅卵石图案。当您更新C_j[x]（ie您从其当前值增加其分数）然后记住导致更新的初始和后续模式为P_j[x]=i。也就是说“模式x给出了最好的结果，考虑到前面的模式i”。

全部完成后，只需找到得分最高的模式。然后，您可以使用P_j进行回溯，以从导致此结果的每个列中恢复卵石图案。