轉換樸素遞歸硬幣問題時記憶錯誤

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

上面的程式碼工作正常。

但是，當我透過實現記憶化（見下文或在操場上）來改進此解決方案時，我得到了錯誤的答案。

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)

以上是轉換樸素遞歸硬幣問題時記憶錯誤的詳細內容。更多資訊請關注PHP中文網其他相關文章！