c++ - 消除积木方案

Question

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

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

问题:后来我被问到是否可以在 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

然后循环考虑当前玩家拿第一 block 和第二 block ，第二 block 和第三 block 等等。这意味着对手将不得不处理两堆尺寸:

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 对两堆都有获胜策略，则返回真。如果是，我们不想选择那个，所以我们否定它，返回 false。如果不是，通过否定它我们得到 true，并且通过 ORing 所有值，我们找出是否有一个 true，我们可以选择。