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

php小编鱼仔在解决朴素递归硬币问题时，不小心犯了一个记忆错误。这个问题是指给定一定数量的硬币和一个目标金额，要求计算出组成目标金额的所有不同组合方式。通常，我们可以使用递归来解决这个问题，但我的记忆错误导致了错误的计算结果。在这篇文章中，我将重新解释正确的解决方法，并提供一些实用的技巧来避免类似的错误。

问题内容

我正在尝试解决以下问题：

两名玩家从一堆硬币开始，每个玩家都可以选择从硬币堆中取出一枚或两枚硬币。拿走最后一枚硬币的玩家就输了。

我想出了以下简单的递归实现 （游乐场）：

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

上面的代码工作正常。

SEEK.ai

AI驱动的智能数据解决方案，询问您的任何数据并立即获得答案

下载

但是，当我通过实现记忆化（见下文或在操场上）来改进此解决方案时，我得到了错误的答案。

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

任何关于为什么第二个实现返回与第一个实现不同的值的帮助将不胜感激！

解决方法

你的记忆是错误的：获胜者不仅取决于当前的硬币数量，还取决于轮到谁。您需要类似以下内容：

type state struct {
    coinsRemaining int
    currentPlayer string
}
memo := make(map[state]string)