Stone Game III

Stone Game III is a game-theory DP. Two players play optimally and you must predict who wins. The trick that makes it tractable is to stop tracking two separate scores and track a single number instead: the score difference the player to move can force.

The slow way first

The naive idea is to simulate every choice both players could make, branching 3 ways each turn. That is exponential — O(3^n) — and recomputes the same suffixes again and again.

The question to ask: what does a player actually care about? Not the two totals separately, but the gap between them. If from some position the player to move can force a final lead of d, that single number captures everything about that position.

The idea: track the score difference

Let dp[i] be the best (my total − opponent total) the player to move can guarantee using only stones[i:]. When it is your turn at i, you take k stones (k in 1..3). You collect their sum, and then your opponent is the one to move from i + k — so from your point of view their forced difference dp[i + k] counts against you.

So dp[i] = max over k in 1..3 of (sum(stones[i..i+k-1]) − dp[i+k]). We fill dp right-to-left from the base case dp[n] = 0. At the end, dp[0] is Alice minus Bob: positive → Alice, negative → Bob, zero → Tie.

Walk through it

Step through the animation. The pointer i moves right-to-left. At each spot we try taking 1, 2, or 3 stones, subtract the opponent's already-computed dp[i+k], and keep the best. For [1, 2, 3, 7] we get dp = [-1, 12, 10, 7, 0]. Since dp[0] = -1 < 0, Bob wins.

Pseudocode

n = number of stones
dp = array of size n+1, all zero        # dp[n] = 0 base case
for i from n-1 down to 0:
    take = 0
    best = -infinity
    for k in 1..3:
        if i + k > n: stop trying larger k
        take = take + stones[i + k - 1]   # running sum of next k stones
        best = max(best, take - dp[i + k])
    dp[i] = best
if dp[0] > 0: return "Alice"
if dp[0] < 0: return "Bob"
return "Tie"

The Python solution

def stone_game_iii(stones):
    n = len(stones)
    dp = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        take = 0
        best = float("-inf")
        for k in range(1, 4):
            if i + k > n:
                break
            take += stones[i + k - 1]
            best = max(best, take - dp[i + k])
        dp[i] = best
    if dp[0] > 0:
        return "Alice"
    if dp[0] < 0:
        return "Bob"
    return "Tie"

• dp has length n + 1; dp[n] = 0 is the base case — no stones left, no difference to force.
• We loop i backwards so dp[i + k] is always already computed before we need it.
• take is the running sum of the next k stones, so we never re-add them.
• take - dp[i + k] is the heart: I gain take, but the opponent then forces dp[i + k] against me.
• dp[i] = best records the best difference the mover can guarantee from i.
• The sign of dp[0] decides the winner — it is Alice minus Bob under optimal play.

Complexity

The inner loop runs at most 3 times, so each of the n positions is constant work: overall O(n) time and O(n) space for the dp array (reducible to O(1) since only the next 3 entries are needed).

When this pattern shows up

Practice