LeetCode 877 — Stone Game (DP)

What does it solve?

Alice and Lee alternate taking piles from either end of a row. Both play optimally. Return true if Alice wins.

The DP state dp[i][j] = the score advantage the current player gains over their opponent on the subarray piles[i..j]. Positive = current player ahead.

Recurrence

// Base: single pile — take it all
dp[i][i] = piles[i]

// Interval: take left or right end
dp[i][j] = max(
piles[i] − dp[i+1][j], // take left
piles[j] − dp[i][j−1] // take right
)

// Alice wins if dp[0][n-1] > 0

💡 Key insight: dp[i][j] represents how much more the current player scores compared to the opponent on range [i..j], assuming both play optimally. When a player takes piles[i], their opponent then plays optimally on [i+1..j] gaining advantage dp[i+1][j] — so the net gain is piles[i] − dp[i+1][j]. We fill small intervals first (diagonal by diagonal) so dependencies are always ready.

Complexity

Time

O(n²)

We fill every cell of an n×n DP table exactly once. Each cell is O(1).

Space

O(n²)

The 2D DP table stores one value per pair (i,j). Can be reduced to O(n) with 1D DP.

Examples & edge cases

Live animation — Interval DP bottom-up fill

Alice (current player advantage) Lee dp cell being filled dependency cells Final answer dp[0][n-1]

Piles — i=— to j=— (current interval)

👤 Alice (first player)

—

waiting...

👤 Lee (second player)

—

waiting...

dp[i][j] table — advantage of current player on piles[i..j]

Step — of —

Current cell

—

dp[i][j]

Interval size

—

j − i + 1 piles

dp[0][n-1]

—

Alice's advantage

Alice wins?

—

dp[0][n-1] > 0?

Select an example and press Play to begin.

✓ Complete!

Speed Medium

Step-by-step DP fill table

Step	i	j	Size	Take left piles[i]	Take right piles[j]	dp[i][j] = max	Meaning

C++ implementation

stone_game.cpp

#include <bits/stdc++.h>
using namespace std;

bool stoneGame(vector<int>& piles) {
    int n = piles.size();
    // dp[i][j] = advantage of current player on piles[i..j]
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // Base case: single pile — current player takes it all
    for (int i = 0; i < n; i++)
        dp[i][i] = piles[i];

    // Fill by increasing interval size
    for (int size = 2; size <= n; size++) {
        for (int i = 0; i + size - 1 < n; i++) {
            int j = i + size - 1;
            // Take left: gain piles[i], opponent gets dp[i+1][j]
            int takeLeft  = piles[i] - dp[i + 1][j];
            // Take right: gain piles[j], opponent gets dp[i][j-1]
            int takeRight = piles[j] - dp[i][j - 1];
            dp[i][j] = max(takeLeft, takeRight);
        }
    }
    // Alice wins if she has positive advantage over full array
    return dp[0][n - 1] > 0;
}

int main() {
    vector<int> piles = {5, 3, 4, 5};
    cout << (stoneGame(piles) ? "Alice wins" : "Lee wins"); // Alice wins
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars