algorithm - 跳棋板 - DP

Question

给定一个有 4 行和 N 列的棋盘。矩阵中的每个单元格都有一个值。给定需要放置在棋盘上的 2N 个标记(每个标记在一个单元格上)，因此矩阵单元格中所有值的总和将尽可能大(最大值)。

放置 token 的限制是两个 token 不能水平或垂直相邻。

您不必放置所有的 2N 标记。

一列中有八种合法的标记方式，所以我定义了 8 个大小为 N 的数组，每个数组描述一个选项。

无论如何，使用动态规划，我需要为问题建立一个递归方程。

我想到了:

A(i,j) = max { A(i,j) , A(i,j) + max { A(i-1,j-1) , ... , H(i-1,j-1) } } , B(i,j) = .... , H(i,j) = ...

当A是第一个数组，H是第8个数组时。

现在，我不认为我的递归方程是好的。即使是，我也不知道如何将条件(两个标记不能水平或垂直相邻)添加到递归方程中。

有人可以帮忙吗？

Answer 1

是的，您有 8 种可能的方式在列中放置标记:

A B C D E F G H
e *       *   *
m   *       *
p     *   *
t       *   * *
y

现在，您只能在其他列之后放置特定的列。例如:

1. A 可以是任何列的邻居，
2. 只有A可以是自己的邻居，
3. B 可以是 C 和 G 的邻居，但不能是另一个 B 或F 或 H,
4. H只能是A、C或D等的邻居

需要注意的一件事是，如果给定的列与 F 和 G 相邻，则 A 会很有用。

所以我们有一个(无向)图:

  A B C D E F G H
A + + + + + + + +
B + - + + + - + -
C + + - + + + - +
D + + + - + - + +
E + + + + - + - -
F + - + + + - + -
G + + - + - + - -
H + - + + - - - -

以上是关联矩阵。

之后，我们将 A(i) 定义为如果 i th，我们可以从前 i 列获得的最大可能总和列以类型 A 标记放置结束。 B、C、...、H 也是如此。

然后你有一个递归公式:

X(i+1) = {max Y(i) where X and Y can be neighboring columns} + 
         {sum of the cells in the i+1 column for placement X}

这里 X 遍历所有可能的位置 A, B, C, ..., H.

初始值为A(0) = 0, B(0) = 0, ..., H(0) = 0。

最终答案是max{ A(N), B(N), C(N), D(N), ..., H(N) }。

注意:

以上是解决方案，或者思路，实现可以不同。例如，您可以对所有内容进行硬编码(假设 Board[i][j] 是放置在棋盘上的值，索引从 0 开始):

F(i+1) = max{ A(i), C(i), E(i), G(i) } +  // This is from the matrix above
         Board[0][i+1] + Board[2][i+1]    // This is from the definition of F type column

并且每个字母都相似。您不必将关联矩阵作为程序中的真实实体，只需在构造表达式时将其牢记在心即可。