python - 用动态规划来拼棋盘

Question

我正在尝试自学动态编程，并在麻省理工学院遇到了这个问题。

给定一个 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 个元素的独立数组。

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

Answer 1

您走在正确的轨道上。当您检查每个新列时，您将最终计算到该点的所有可能的最佳分数。

假设您构建了兼容性列表(一个二维数组)并将其命名为 L_i[y] 这样对于每个模式 i存在一个或多个兼容模式L_i[y]。

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

此外，您还存储了导致每个分数的鹅卵石图案。当您更新 C_j[x](即，您将其得分从其当前值增加)时，请记住导致更新为 P_j[x] = i。也就是说，“给定前面的模式 i，模式 x 给出了最好的结果”。

当你全部完成后，只需找到得分最高的模式 i C_n[i]。然后，您可以使用 P_j 回溯，从导致此结果的每一列中恢复鹅卵石图案。