考虑一排价值为v1，v2……，vn的硬币。我们轮流与对手比赛。在每一回合中，玩家从一排硬币中选择第一枚或最后一枚，将其永久移除，并获得硬币的价值。如果我们先走，确定我们能赢得的最大金额。
我的解决方案
既然我们先走，我们可以选择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 + 1），然后，我的对手可以选择第一个[ i + 2 ]或最后一个，我希望在下一次我选择的时候有最大值，因此第一个在外max中。
第二个与上述类似，如果我选择最后一个[j-1 ]，对手选择第一个[i+1]或最后一个[j-2]，我下一次将它最大化。
现在，在书中我看到递归是
M(i,j) = Max{ Min{ Same } + vi, Min{ Same } + vj }
现在，为什么我要最小化这里。这不等同于说我第一次不得不选择最大化，但第二次我必须选择最小化。
我做错什么了？
谢谢。
最佳答案
如果你想计算你一定能赢的钱，你必须假设你的对手试图最大化他/她自己的结果，这等于最小化你的结果（因为你的收益总和总是等于v1 + ... + vn）。你的计算公式是，如果你的对手总是（从他/她的角度）做出错误的举动，你就能赢。
关于algorithm - 硬币游戏的最佳策略，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17988177/