原始问题陈述 Pile it up
总结:两个玩家 A 和 B 玩一个由 2 堆 X 和 Y 硬币组成的游戏。每个回合他都可以执行以下操作之一:
- 从一堆中取出任意数量的硬币(至少 1 个硬币)
- 从两堆中取出相同数量的硬币
- 通过转弯。这仍然算作一圈。
当无法移动且无法移动的玩家失败时，游戏结束。两名球员都表现出色。双方选手在比赛开始前计算比赛结果。失败的玩家试图最大化游戏中的回合数，而获胜的玩家则试图最小化回合数。没有玩家可以传球超过 P 次。 A开始比赛。输出获胜者的名字和游戏中的步数，用一个空格分隔。 0 <= X, Y, P <= 1000
我想出了一个 O(n^3) DP 解决方案，但考虑到边界，它肯定不足以解决这个问题。令 d[i, j] 为如果轮到你玩并且 X 堆和 Y 堆中分别剩下 i 和 j 个硬币时获胜的最少回合数。然后我们有:
d[i, j] = 0 if i = j = 0
1 if (i = 0 && j > 0) or (i > 0 && j = 0) or (i = j && i > 0)
min(min(d[i-p, j]), min(d[i, j-q), min(i-r, j-r)) if a each substate is a losing position
max of all winning position substate if no losing substate is found
最后，d[i,j] = d[i,j] + 2*P if [i,j] 是获胜状态，您不会从一开始就立即获胜。
从上面的公式可以看出，这是一个复杂度为 O(n^3) 的解决方案。我想改进 O(n^2) 的解决方案，如何重新表述问题？
最佳答案
第一中奖位置是
- 1 个空桩
- 两堆硬币数量相同
玩家什么时候结束他的回合？
假设position是(3,2)，那么他有3种选择。
- 他可以移动到 (2,2) 但这对他的对手来说是一个获胜的位置。
- 他可以移动到 (1,0)，但这对他的对手来说也是一个获胜的位置。
- 如果他选择跳过回合，那么对手也可以跳过这个回合。这个跳过最多可以进行P回合。
根据 P 的奇偶性(P 是偶数还是奇数)以及谁开始跳过序列，我们可以找出获胜者。从那里找到轮数并不难。
为什么跳跃顺序是最优的？
好吧，如果你输了，你会想在游戏中停留更长时间。(根据游戏规则。)所以即使我知道基于 P 的平价我会输，我可以延迟 P 回合.有道理吗？
我鼓励您利用这一见解来加快算法速度，但如果您在实现算法时遇到困难，请务必提出问题!
关于algorithm - 如何改进这个动态规划解决方案？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17519722/