消除方块程序

Question

今天早上我参加了一个技术讨论，主席邀请我和他一起玩一个游戏。

有"n"块的序列，每个玩家都有机会选择2个相邻的块，并将它们标记为已填满。玩家们继续这样做，直到最后一对相邻的方块被填满。填满最后一对的人输掉游戏。

问题:后来有人问我是否可以用c++编写一个程序，在每次机会时向每个玩家提供提示，以确定考虑到当前棋盘的状态，可用的对子中哪一对会给他最大的获胜机会。

我肯定有一个设计/算法。只是我无法识别它。你能给我一个解决这个问题的可能方法吗?是否存在涵盖类似问题(如分区问题)的既定问题

Answer 1

我认为我们可以使用动态规划。让:

dp[n, 1] = true    if player 1 has a certain winning strategy for n blocks
           false   otherwise
dp[n, 2] = same for player 2

玩家1先移动。

我们:

dp[0, 1] = dp[0, 2] = true
dp[1, 1] = dp[1, 2] = true
dp[2, 1] = false, dp[2, 2] = true

然后递归考虑当前玩家拿走了第一个和第二个块，第二个和第三个等等。这意味着对手必须处理两堆大小的牌:

0, n - 2
1, n - 3
2, n - 4
...
k, n - k - 2, k = 0 to n - 2

对于一个玩家来说，他们必须至少有一个获胜策略。

对于当前玩家来说，他必须能够将对手带到他们的dp是false的状态。我们输入:

dp[n, 1] =       OR         {NOT (dp[k, 2] OR dp[n - k - 2, 2])} 
           0 <= k <= n - 2
dp[n, 2] =       OR         {NOT (dp[k, 1] OR dp[n - k - 2, 1])} 
           0 <= k <= n - 2

意味着dp[n, 1]是真的，如果我们可以让下一个玩家进入一个他没有确定的获胜策略的状态。当然，我们的对手也会打出最佳状态。

dp[k, 2] OR dp[n - k - 2, 2]

如果玩家2对两摞牌都有获胜策略，则返回true。如果是，我们不想选择它，所以我们将它取反，返回false。如果不是，通过否定它我们得到真，通过对所有值进行OR，我们发现是否有一个真，我们可以选择。