跳棋板- DP

Question

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

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

您不需要放置所有的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都是相邻的，则G可能很有用。

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

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

以上是关联矩阵。

在此之后，我们将A(i)定义为如果i th列以一个类型的A令牌放置结束，我们可以从第一个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

每封信都是一样的。您不必将关联矩阵作为程序中的真实实体，只需在构造表达式时考虑它。