algorithm - 硬币游戏的最优策略

Question

考虑一排 n 枚值(value) v1,v2.......,vn 的硬币。我们交替轮流与对手进行游戏。在每一轮中，玩家从该行中选择第一枚硬币或最后一枚硬币，将其永久移除，并获得硬币的值(value)。确定如果我们先行动，我们肯定能赢得的最大可能金额。

我的解决方案

因为我们先走，所以我们可以选择 v1 或 v2，然后我们的对手可以选择从头开始或从头开始。因此可能出现的四个子问题是。

(1,1) , (1,2), (2,1), (2,2)

其中 (1,1) 表示我从开始选择 [即1] 并且对手也从开始选择 [即 1]。

(1,2) 表示我从头开始选择，而对手选择最后一个。

因此，如果 M(i,j) 是我可以选择的 (i,j) 上的最大值，则将 (i,j) 表示为递归函数。

M(i,j) = Max{ Max{ M(i+2,j), M(i+1,j-1) } + vi, Max{ M(i+1,j-1), M(i,j-2) } + vj }

解释:当我有 i..j 个元素时，我可以选择第一个 [i+1] ，为此，我的对手可以选择第一个 [i+2] 或最后一个 [j- 1]，我希望在下次选择时获得最大值，因此第一项位于外部 Max 内。

第二个与上面的类似，即如果我选择最后一个 [j-1]，对手选择第一个 [i+1] 或最后一个 [j-2]，我下次将其最大化。

现在，在书中我看到了递归

M(i,j) = Max{ Min{ Same } + vi, Min{ Same } + vj }

现在，为什么我要在这里最小化。是不是等于说第一次最大化我得挑，第二次最小化我得挑。

我做错了什么？谢谢。

Answer 1

如果你想计算你可以肯定赢的钱数，你必须假设你的对手试图最大化他/她自己的结果，这相当于最小化 你的(因为你的 yield 总和总是等于 v1 + ... + vn)。你的公式计算的是如果你的对手总是走错(从他/她的角度来看)你能赢多少。