我正在尝试自学动态编程，并从麻省理工学院遇到了这个问题。
我们得到一个棋盘，它有 4 行 n 列，每个方格中写有一个整数。我们还得到了一组 2n 颗鹅卵石，我们想将其中的一部分或全部放在棋盘上（每个鹅卵石可以正好放在一个方格上），以使被覆盖的方格中的整数和最大化鹅卵石。有一个限制：要合法放置鹅卵石，它们中的任何一个都不能位于水平或垂直相邻的方格上（对角相邻是可以的）。
(a) 确定可以在任何列中出现的合法模式的数量（孤立地，忽略相邻列中的鹅卵石）并描述这些模式。如果两个模式可以放置在相邻的列上以形成合法放置，则称它们兼容。让我们考虑由前 k 列 1 k n 组成的子问题。每个子问题都可以分配一个类型，即最后一列中出现的模式。
(b) 使用兼容性和类型的概念，给出一个 O(n) 时间的动态规划算法来计算一个最佳位置。
好的，所以对于 a 部分：有 8 种可能的解决方案。
对于 b 部分，我不确定，但这就是我要去的地方：拆分为子问题。假设 i 在 n 中。1. 将 Cj[i] 定义为最佳值，方法是对列 0,...,i 进行 pebling，使列 i 具有模式类型 j。2. 为每种模式类型创建 8 个单独的包含 n 个元素的数组。
我不知道从这里去哪里。我意识到网上有这个问题的解决方案，但解决方案对我来说似乎不是很清楚。