Memory error when converting naive recursive coin problem

php Xiaobian Yuzai accidentally made a memory error when solving the simple recursive coin problem. This problem is given a certain number of coins and a target amount, and is required to calculate all the different combinations that make up the target amount. Normally, we could use recursion to solve this problem, but my memory error resulted in incorrect calculations. In this article, I will re-explain the correct solution and provide some practical tips to avoid similar mistakes.

Question content

I'm trying to solve the following problem:

Two players start with a pile of coins, and each player can choose to take one or two coins from the pile. The player who takes the last coin loses.

I came up with the following simple recursive implementation (Amusement Park):

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 in the playground), 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 on why the second implementation returns a different value than the first implementation would be greatly appreciated!

Solution

Your memory is wrong: the winner depends not only on the current number of coins, but also on whose turn it is. You need something like:

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

The above is the detailed content of Memory error when converting naive recursive coin problem. For more information, please follow other related articles on the PHP Chinese website!