递归取币问题优化：Memoization实现异常排查

问题背景 #

两名玩家从一堆硬币开始，每人可选择移除1枚或2枚硬币，取走最后一枚硬币的玩家落败。

正确的朴素递归实现 #

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"
}

这段代码运行正常，输入4枚硬币、当前玩家为"you"时，返回结果为"them"。

错误的记忆化优化实现 #

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))
}

这段记忆化实现返回的结果与朴素递归不一致。

错误原因分析 #

你的记忆化实现只以coinsRemaining作为缓存的key，但实际上当前玩家是谁也会影响结果——相同硬币数量下，当前玩家是"you"还是"them"，对应的获胜者可能完全不同。

举个例子：

• 当coinsRemaining=1，当前玩家是"you"时，你必须取走最后1枚硬币，直接落败，返回结果是"them"；
• 但如果coinsRemaining=1，当前玩家是"them"时，他们必须取走最后1枚硬币，你获胜，返回结果是"you"。

但你的缓存只存了coinsRemaining对应的结果，第一次计算后就会错误复用这个值，导致后续不同玩家的调用拿到错误的缓存结果。

修复方案 #

把缓存的key改成硬币数量+当前玩家的组合，比如用fmt.Sprintf("%d_%s", coinsRemaining, currentPlayer)作为map的key。修改后的代码示例：

import "fmt"

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

    key := fmt.Sprintf("%d_%s", coinsRemaining, currentPlayer)
    if val, exists := memo[key]; exists {
        return val
    }

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

    result := nextPlayer
    if gameWinner(coinsRemaining-1, nextPlayer, memo) == currentPlayer || gameWinner(coinsRemaining-2, nextPlayer, memo) == currentPlayer {
        result = currentPlayer
    }

    memo[key] = result
    return result
}

func main() {
    memo := make(map[string]string)
    fmt.Println(gameWinner(4, "you", memo)) // 正确输出 "them"
}

内容的提问来源于stack exchange，提问作者testing09