Stone Game II

medium dynamic programming game theory suffix sum

Problem

Alice and Bob take turns over a row of stone piles, Alice first. On a turn the player takes all stones from the first X remaining piles, where 1 ≤ X ≤ 2M. Then M becomes max(M, X). M starts at 1. Both play optimally; return the maximum number of stones Alice can collect.

Inputpiles = [2, 7, 9, 4, 4]

Output10

If Alice takes 1 pile she gets 2, then Bob can take up to 2 piles. Playing optimally Alice secures 2 + 4 + 4 = 10.

piles (comma-separated)

def stone_game_ii(piles):
    n = len(piles)
    suffix = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix[i] = suffix[i + 1] + piles[i]
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dfs(i, m):
        if i + 2 * m >= n:
            return suffix[i]
        best = 0
        for x in range(1, 2 * m + 1):
            best = max(best, suffix[i] - dfs(i + x, max(m, x)))
        return best

    return dfs(0, 1)

function stoneGameII(piles) {
  const n = piles.length;
  const suffix = new Array(n + 1).fill(0);
  for (let i = n - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + piles[i];
  const memo = new Map();
  function dfs(i, m) {
    if (i + 2 * m >= n) return suffix[i];
    const key = i * 200 + m;
    if (memo.has(key)) return memo.get(key);
    let best = 0;
    for (let x = 1; x <= 2 * m; x++)
      best = Math.max(best, suffix[i] - dfs(i + x, Math.max(m, x)));
    memo.set(key, best);
    return best;
  }
  return dfs(0, 1);
}

class Solution {
    int[] suffix;
    Integer[][] memo;
    int n;
    public int stoneGameII(int[] piles) {
        n = piles.length;
        suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + piles[i];
        memo = new Integer[n][n + 1];
        return dfs(0, 1);
    }
    int dfs(int i, int m) {
        if (i + 2 * m >= n) return suffix[i];
        if (memo[i][m] != null) return memo[i][m];
        int best = 0;
        for (int x = 1; x <= 2 * m; x++)
            best = Math.max(best, suffix[i] - dfs(i + x, Math.max(m, x)));
        return memo[i][m] = best;
    }
}

class Solution {
    int n;
    vector<int> suffix;
    vector<vector<int>> memo;
    int dfs(int i, int m) {
        if (i + 2 * m >= n) return suffix[i];
        if (memo[i][m] != -1) return memo[i][m];
        int best = 0;
        for (int x = 1; x <= 2 * m; x++)
            best = max(best, suffix[i] - dfs(i + x, max(m, x)));
        return memo[i][m] = best;
    }
public:
    int stoneGameII(vector<int>& piles) {
        n = piles.size();
        suffix.assign(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + piles[i];
        memo.assign(n, vector<int>(n + 1, -1));
        return dfs(0, 1);
    }
};

Explanation

Both players play optimally, so this is a minimax game. The clever framing is that on each turn the current player takes some prefix of the remaining piles, and after that the other player faces the very same kind of problem on what is left. So we describe a state by where we start (i) and the current limit parameter (m).

dfs(i, m) returns the most stones the player to move can collect from piles i..n-1. They may take the first X piles for any 1 ≤ X ≤ 2M, and then M updates to max(M, X) for the opponent.

The key trick uses a suffix sum: suffix[i] is the total of all remaining stones. If the opponent then plays optimally and grabs dfs(i + X, max(m, X)), the current player's share is suffix[i] - dfs(...). We try every X and keep the best. If i + 2M already reaches the end, the player simply takes everything: suffix[i].

Example: piles = [2,7,9,4,4]. Playing this out, Alice can guarantee 2 + 4 + 4 = 10, so dfs(0, 1) returns 10.

Memoization over (i, m) states avoids recomputation, giving the polynomial running time instead of exponential.

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