#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/game-theory-dp/stone-game-ii-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/game-theory-dp/stone-game-ii-implementation

Repovive

LeetCode 1140 Stone Game II - Implementation - Game Theory DP | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 1140 Stone Game II - Implementation

With suffix sums

Here's the full solution:

function stoneGameII(piles)
    n := length of piles
    suffix := array of size n + 1
    suffix[n] := 0
    for i := n - 1 down to 0
        suffix[i] := suffix[i + 1] + piles[i]
    dp := 2D (two-dimensional) array [n + 1][n + 1], all -1
    return solve(0, 1)

function solve(i, M)
    if i >= n then
        return 0
    if i + 2 * M >= n then
        return suffix[i]
    if dp[i][M] != -1 then
        return dp[i][M]
    best := 0
    for X := 1 to 2 * M
        opponent := solve(i + X, max(M, X))
        myStones := suffix[i] - opponent
        best := max(best, myStones)
    dp[i][M] := best
    return best

Time: $O(n^3)$ . Space: $O(n^2)$ .

Time complexity: $O(n^3)$ .

Space complexity: $O(n^2)$ .