英文:
Memoization error when converting naive recursive coin problem
问题
我正在尝试解决以下问题：
两个玩家从一堆硬币开始，每个玩家可以选择从堆中取走一枚或两枚硬币。取走最后一枚硬币的玩家将输掉游戏。
我提出了以下的朴素递归实现（playground）：
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"
}
上述代码运行正常。
然而，当我通过实现记忆化来改进这个解决方案时（见下方或playground），我得到了错误的答案。
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))
}
任何关于为什么第二个实现返回与第一个实现不同的值的帮助将不胜感激！
英文:
I am attempting the following problem:
Two players start with a pile of coins, and each player has the choice of removing either one or two coins from the pile. The player who removes the last coin loses.
I have come up with the following naive, recursive implementation
(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"
}
The above code works fine.
However, when I improve this solution by implementing memoization (see below, or on the playgound), I get the wrong answer.
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))
}
Any help as to why the second implementation is returning different values to the first would be greatly appreciated!
答案1
得分: 1
你的记忆化有误：胜利者不仅取决于当前硬币数量，还取决于轮到谁的回合。你需要像下面这样的代码：
type state struct {
coinsRemaining int
currentPlayer string
}
memo := make(map[state]string)
英文:
Your memoization is wrong: the winner does not only depend on the current number of coins, but also on whose turn it is. You need something like the following:
type state struct {
coinsRemaining int
currentPlayer string
}
memo := make(map[state]string)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论