algorithm - 硬币游戏问题输入为 7 时的获胜方式数

Question

我正在研究经典的投币游戏问题:
爱丽丝和鲍勃正在使用一堆硬币玩游戏。玩家依次从一堆硬币中挑选几枚硬币。每次允许玩家挑选 1、2 或 4 个硬币，获得最后一个硬币的玩家为赢家。爱丽丝选择第一个。
我其实不明白结果是怎么来的。

    coinGame(1)= ('Alice', 1)
    coinGame(2) = ('Alice', 1)
    coinGame(3) = ('Bob', 2)
    coinGame(4) = ('Alice', 3)
    coinGame(5) = ('Alice', 2)
    coinGame(6) = ('Bob', 6)
    coinGame(7) = ('Alice', 8).

我理解1,2,3...6的输出，但我不理解7及之后的输出。
对于输入 6，由于 Alice 总是会到达硬币 2、4 和 5。因此，Bob 只需选择 1、2 或 4 中的任意一个即可赢得游戏。总的方式是 1 + 3 + 2 = 6对于输入 7，Bob 可以达到 3 和 6，然后 Alice 只需选择 4 或 1 个硬币即可赢得游戏，有 2 + 6 = 8 种获胜方式。我不明白的是，对于输入7，爱丽丝也可以达到5，然后鲍勃只是选择2获胜。为什么我们忽略了这个案例并认为 Alice 赢了？

我希望我能得到一些澄清。

谢谢!

Answer 1

一个关键点
如果鲍勃赢了比赛，那么开始比赛的人就会失去一些策略。
如果 Alice 赢了游戏，那么开始游戏的人就赢了。

所以从每个N中检查N-1、N-2、N-4中是否有Bob获胜的位置。如果是，那么 Alice 将以 Bob 获胜的位置总和获胜。

如果爱丽丝从 N-1、N-2 和 N-4 中获胜，那么爱丽丝肯定会输给 N。
因为从位置 N-1、N-2 和 N-4 开始游戏的人赢得了游戏。当 Alice 将回合传给 Bob 时，Bob 将只获得 N-1、N-2 和 N-4 中的一个。从这些位置开始游戏的人将赢得比赛。

N>=5
sum=0
if Bob wins in N-1
    sum+=coinGame(N-1).count
if Bob wins in N-2
    sum+=coinGame(N-2).count
if Bob Wins in N-4 
    sum+=coinGame(N-4).count

if sum==0
   Bob wins with coinGame(N-1).count + coinGame(N-2).count + coinGame(N-4).count
else
   Alice wins with sum

寻找coinGame(7)
鉴于coinGame(3) = ('Bob', 2) 7-4
coinGame(5) = ('爱丽丝', 2) 7-2
coinGame(6) = ('Bob', 6) 7-1

鲍勃从 6 开始计数 6 和从 3 计数 2 赢得比赛
所以爱丽丝将从 7 数到 8 赢得比赛