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

IT行业相对于一般传统行业，发展更新速度更快，一旦停止了学习，很快就会被行业所淘汰。所以我们需要踏踏实实的不断学习，精进自己的技术，尤其是初学者。今天golang学习网给大家整理了《转换朴素递归硬币问题时记忆错误》，聊聊，我们一起来看看吧！

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

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

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

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

上面的代码工作正常。

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

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)

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于Golang的相关知识，也可关注golang学习网公众号。