Stone Game V

hard dp interval dp prefix sum memoization

Problem

Each round Alice splits the current row of stoneValue into a left and right part. Bob throws away the part with the larger sum; Alice scores the smaller sum and continues with that part (ties: Alice chooses). The game ends when one stone is left. Return Alice's maximum total score.

InputstoneValue = [6,2,3,4,5,5]

Output18

dp[l][r] = best score Alice can get from the subarray l..r, choosing the split that maximizes smaller-half + dp(that half).

stoneValue

def stone_game_v(stoneValue):
    n = len(stoneValue)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + stoneValue[i]
    from functools import lru_cache

    @lru_cache(None)
    def solve(l, r):
        if l == r:
            return 0
        best = 0
        for m in range(l, r):
            left = prefix[m + 1] - prefix[l]
            right = prefix[r + 1] - prefix[m + 1]
            if left < right:
                best = max(best, left + solve(l, m))
            elif left > right:
                best = max(best, right + solve(m + 1, r))
            else:
                best = max(best, left + solve(l, m), right + solve(m + 1, r))
        return best

    return solve(0, n - 1)

function stoneGameV(stoneValue) {
  const n = stoneValue.length;
  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stoneValue[i];
  const memo = new Map();
  function solve(l, r) {
    if (l === r) return 0;
    const key = l * n + r;
    if (memo.has(key)) return memo.get(key);
    let best = 0;
    for (let m = l; m < r; m++) {
      const left = prefix[m + 1] - prefix[l];
      const right = prefix[r + 1] - prefix[m + 1];
      if (left < right) best = Math.max(best, left + solve(l, m));
      else if (left > right) best = Math.max(best, right + solve(m + 1, r));
      else best = Math.max(best, left + solve(l, m), right + solve(m + 1, r));
    }
    memo.set(key, best);
    return best;
  }
  return solve(0, n - 1);
}

class Solution {
    int[] prefix;
    Integer[][] memo;
    public int stoneGameV(int[] stoneValue) {
        int n = stoneValue.length;
        prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stoneValue[i];
        memo = new Integer[n][n];
        return solve(0, n - 1);
    }
    int solve(int l, int r) {
        if (l == r) return 0;
        if (memo[l][r] != null) return memo[l][r];
        int best = 0;
        for (int m = l; m < r; m++) {
            int left = prefix[m + 1] - prefix[l];
            int right = prefix[r + 1] - prefix[m + 1];
            if (left < right) best = Math.max(best, left + solve(l, m));
            else if (left > right) best = Math.max(best, right + solve(m + 1, r));
            else best = Math.max(best, Math.max(left + solve(l, m), right + solve(m + 1, r)));
        }
        return memo[l][r] = best;
    }
}

class Solution {
    vector<int> prefix;
    vector<vector<int>> memo;
    int solve(int l, int r) {
        if (l == r) return 0;
        if (memo[l][r] != -1) return memo[l][r];
        int best = 0;
        for (int m = l; m < r; m++) {
            int left = prefix[m + 1] - prefix[l];
            int right = prefix[r + 1] - prefix[m + 1];
            if (left < right) best = max(best, left + solve(l, m));
            else if (left > right) best = max(best, right + solve(m + 1, r));
            else best = max({best, left + solve(l, m), right + solve(m + 1, r)});
        }
        return memo[l][r] = best;
    }
public:
    int stoneGameV(vector<int>& stoneValue) {
        int n = stoneValue.size();
        prefix.assign(n + 1, 0);
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stoneValue[i];
        memo.assign(n, vector<int>(n, -1));
        return solve(0, n - 1);
    }
};

Explanation

The state that matters is "which contiguous slice of stones are we still playing with", so we define dp[l][r] = the maximum total Alice can still earn from the subarray l..r. This is classic interval DP.

From a slice, Alice picks a split point m between l and r-1. Bob discards the heavier half, so Alice keeps the lighter one and adds its sum to her score, then recurses into that surviving half. To compare halves fast we precompute a prefix sum so any range sum is one subtraction.

For each split there are three cases. If the left sum is smaller, Alice scores left + dp[l][m]. If the right is smaller, she scores right + dp[m+1][r]. On a tie she may keep either side, so we take the better of the two.

Alice tries every split and keeps the maximum. We memoize dp[l][r] so each interval is solved once; with O(n) intervals' worth of subproblems each scanning O(n) splits, the work is O(n²) states with an O(n) loop, i.e. O(n³).

Example: [6,2,3,4,5,5]. Working through the splits with memoization gives Alice a best total of 18.

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