Go 转换朴素递归硬币问题时的记忆错误

我正在try 解决以下问题:

两个玩家从一堆硬币开始，每个玩家可以 Select 从一堆硬币中取出一枚或两枚硬币.拿出最后一枚硬币的玩家输了.

我想出了以下幼稚的递归实现 (playgound):

func gameWinner(coinsRemaining int, currentPlayer string) string {
    if coinsRemaining <= 0 {
        return currentPlayer
    }

    var nextPlayer string

    if currentPlayer == "you" {
        nextPlayer = "them"
    } else {
        nextPlayer = "you"
    }

    if gameWinner(coinsRemaining-1, nextPlayer) == currentPlayer || gameWinner(coinsRemaining-2, nextPlayer) == currentPlayer {
        return currentPlayer
    } else {
        return nextPlayer
    }
}

func main() {
  fmt.Println(gameWinner(4, "you")) // "them"
}

上面的代码运行良好.

然而，当我通过实现备忘录来改进这个解决方案时(见下文，或on the playgound)，我得到了错误的答案.

func gameWinner(coinsRemaining int, currentPlayer string, memo map[int]string) string {
    if coinsRemaining <= 0 {
        return currentPlayer
    }

    var nextPlayer string

    if currentPlayer == "you" {
        nextPlayer = "them"
    } else {
        nextPlayer = "you"
    }

    if _, exists := memo[coinsRemaining]; !exists {
        if gameWinner(coinsRemaining-1, nextPlayer, memo) == currentPlayer || gameWinner(coinsRemaining-2, nextPlayer, memo) == currentPlayer {
            memo[coinsRemaining] = currentPlayer
        } else {
            memo[coinsRemaining] = nextPlayer
        }
    }

    return memo[coinsRemaining]
}

func main() {
    memo := make(map[int]string)
    fmt.Println(gameWinner(4, "you", memo))
}

任何关于第二个实现返回不同值给第一个实现的帮助都将不胜感激！