Stone Game VII

medium dp interval minimax

Problem

Two players play optimally on a row of stones. On each turn the player removes the leftmost or rightmost stone and gains points equal to the SUM of remaining stones. Alice goes first; return the difference Alice − Bob she can guarantee.

Inputstones = [5,3,1,4,2]

Output6

Best play yields Alice−Bob = 6.

stones

def stone_game_vii(stones):
    n = len(stones)
    prefix = [0]
    for x in stones:
        prefix.append(prefix[-1] + x)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            sum_ij = prefix[j + 1] - prefix[i]
            # remove stones[i] -> opponent plays on [i+1..j], gain = sum - stones[i]
            left = (sum_ij - stones[i]) - dp[i + 1][j]
            right = (sum_ij - stones[j]) - dp[i][j - 1]
            dp[i][j] = max(left, right)
    return dp[0][n - 1]

function stoneGameVII(stones) {
  const n = stones.length;
  const prefix = [0];
  for (const x of stones) prefix.push(prefix[prefix.length - 1] + x);
  const dp = Array.from({length: n}, () => new Array(n).fill(0));
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len <= n; i++) {
      const j = i + len - 1;
      const sumIj = prefix[j + 1] - prefix[i];
      const left = (sumIj - stones[i]) - dp[i + 1][j];
      const right = (sumIj - stones[j]) - dp[i][j - 1];
      dp[i][j] = Math.max(left, right);
    }
  }
  return dp[0][n - 1];
}

class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stones[i];
        int[][] dp = new int[n][n];
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1, sumIj = prefix[j + 1] - prefix[i];
                int left = (sumIj - stones[i]) - dp[i + 1][j];
                int right = (sumIj - stones[j]) - dp[i][j - 1];
                dp[i][j] = Math.max(left, right);
            }
        }
        return dp[0][n - 1];
    }
}

int stoneGameVII(vector<int>& stones) {
    int n = stones.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stones[i];
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            int j = i + len - 1, sumIj = prefix[j + 1] - prefix[i];
            int left = (sumIj - stones[i]) - dp[i + 1][j];
            int right = (sumIj - stones[j]) - dp[i][j - 1];
            dp[i][j] = max(left, right);
        }
    }
    return dp[0][n - 1];
}

Explanation

On each turn a player removes either the leftmost or rightmost stone and scores the sum of the stones that remain. Both play optimally and we want the difference Alice can guarantee. This is classic interval DP: the state is the current sub-row stones[i..j].

dp[i][j] is the best (my score − opponent's score) the player to move can secure on that interval. A prefix sum lets us get the sum of any interval, sum_ij, instantly.

The player removes one end, and the points they earn equal the sum of what's left: removing stones[i] earns sum_ij - stones[i] and hands the opponent interval [i+1, j]; removing stones[j] earns sum_ij - stones[j] and hands over [i, j-1]. The opponent's optimal lead is subtracted, so dp[i][j] = max(left - dp[i+1][j], right - dp[i][j-1]).

We fill the table by increasing interval length so smaller intervals are ready first. Example: stones = [5,3,1,4,2] works out to a guaranteed difference of 6, which is dp[0][n-1].

With n² intervals each handled in constant time, the whole thing runs in O(n²).

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