Stone Game

medium dynamic programming game theory math

Problem

Alice and Bob play with an even number of piles of stones, total odd. On each turn a player takes a whole pile from either end. Both play optimally; Alice goes first. Return true if Alice wins (collects more stones).

Inputpiles = [5, 3, 4, 5]

Outputtrue

Alice takes the last pile (5); whatever Bob does she can guarantee ≥ 10.

piles (comma-separated)

def stone_game(piles):
    n = len(piles)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(piles[i] - dp[i + 1][j],
                           piles[j] - dp[i][j - 1])
    return dp[0][n - 1] > 0

function stoneGame(piles) {
  const n = piles.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = piles[i];
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      dp[i][j] = Math.max(piles[i] - dp[i + 1][j],
                          piles[j] - dp[i][j - 1]);
    }
  }
  return dp[0][n - 1] > 0;
}

boolean stoneGame(int[] piles) {
    int n = piles.length;
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = piles[i];
    for (int len = 2; len <= n; len++)
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = Math.max(piles[i] - dp[i + 1][j],
                                piles[j] - dp[i][j - 1]);
        }
    return dp[0][n - 1] > 0;
}

bool stoneGame(vector<int>& piles) {
    int n = piles.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = piles[i];
    for (int len = 2; len <= n; len++)
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = max(piles[i] - dp[i + 1][j],
                           piles[j] - dp[i][j - 1]);
        }
    return dp[0][n - 1] > 0;
}

Explanation

Each turn a player takes a whole pile from either end of the row, and both play optimally. Rather than tracking two scores, we track the score lead of whoever is about to move. This is an interval DP over sub-ranges piles[i..j].

dp[i][j] is the best (my total − opponent's total) the current player can secure on that range. A single pile is trivial: dp[i][i] = piles[i], since you just take it.

For a longer range you pick the left pile or the right pile. If you take piles[i], the opponent then controls [i+1, j] and earns their own lead dp[i+1][j], which counts against you; same idea for the right. So dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]), filling by increasing length.

Example: piles = [5, 3, 4, 5]. Playing optimally, Alice ends with a positive lead, so dp[0][n-1] > 0 and the function returns true.

The final answer is simply whether dp[0][n-1] > 0: a positive lead means the first player (Alice) collects more stones and wins. There are n² intervals, so it runs in O(n²).

Time: O(n²) Space: O(n²)