给定一个有 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个数组时。
现在,我不认为我的递归方程是好的。即使是,我也不知道如何将条件(两个标记不能水平或垂直相邻)添加到递归方程中。
有人可以帮忙吗?
最佳答案
是的,您有 8 种可能的方式在列中放置标记:
A B C D E F G H
e * * *
m * *
p * *
t * * *
y
现在,您只能在其他列之后放置特定的列。例如:
A
可以是任何列的邻居,- 只有
A
可以是自己的邻居, B
可以是C
和G
的邻居,但不能是另一个B
或F
或H
,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
并且每个字母都相似。您不必将关联矩阵作为程序中的真实实体,只需在构造表达式时将其牢记在心即可。
关于algorithm - 跳棋板 - DP,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16495739/