Problem Description

In the Stone Game V problem, you are given an array of positive integers called stoneValue, where each element represents the value of a stone in a row. Alice and Bob play a game with the following rules:

• Alice starts the game and always plays optimally.
• On her turn, Alice splits the row of stones into two non-empty consecutive parts by choosing an index i (where left = [stoneValue[0], ..., stoneValue[i]] and right = [stoneValue[i+1], ..., stoneValue[n-1]]).
• Alice then compares the sum of values in the left and right parts:
  • If the sum of the left part is less than the right, Alice continues the game on the left part.
  • If the sum of the right part is less than the left, Alice continues on the right part.
  • If the sums are equal, Alice can choose to continue on either part.
• Whenever Alice chooses a part to continue, she earns the sum of the chosen part.
• The process repeats recursively on the chosen part until only one stone remains (no more splits possible).

The goal is to determine the maximum score Alice can obtain by playing optimally from the entire row.

Constraints:

• 1 ≤ stoneValue.length ≤ 500
• 1 ≤ stoneValue[i] ≤ 10⁴

Thought Process

At first glance, the problem appears to involve trying every possible way to split the array at each stage, recursively, and keeping track of the maximum score Alice can achieve. Since Alice can always choose the optimal path, we need to consider all possible splits and, at each step, simulate the game's rules.

A brute-force approach would recursively try every split, but this leads to a huge number of repeated calculations, especially as the array grows. This is a classic case for dynamic programming (DP), where overlapping subproblems can be solved efficiently by storing and reusing results.

The main challenge is:

• Efficiently calculating the sum of subarrays for each split.
• Reusing results for the same subarrays to avoid redundant computation.

Solution Approach

We use a top-down dynamic programming approach with memoization:

1. Precompute Prefix Sums:
   • To quickly get the sum of any subarray, we build a prefix sum array where prefix[i] is the sum of stoneValue[0] to stoneValue[i-1].
2. Recursive DP with Memoization:
   • Define dp(l, r) as the maximum score Alice can achieve from subarray stoneValue[l:r+1].
   • For each possible split point i between l and r:
     • Compute leftSum = sum(l, i), rightSum = sum(i+1, r).
     • If leftSum < rightSum, Alice continues on left and adds leftSum to her score.
     • If rightSum < leftSum, Alice continues on right and adds rightSum to her score.
     • If equal, Alice chooses either side (whichever gives her a better outcome).
   • Store results in a memoization table to avoid recalculating for the same (l, r) range.
3. Base Case:
   • If l == r, there's only one stone left, so the score is 0.
4. Return the DP result for the full array:
   • Start with dp(0, n-1) where n is the length of stoneValue.

This approach ensures that each subproblem is solved only once, making the solution efficient even for the upper constraint of 500 stones.

Example Walkthrough

Let's walk through an example with stoneValue = [6,2,3,4,5,5]:

1. Initial call: dp(0,5) (full array).
2. Try splitting at each possible index:
   • Split at 0: left = [6] (sum=6), right = [2,3,4,5,5] (sum=19). Since 6 < 19, Alice continues on [6], adds 6 to score, but [6] is a single stone so recursion ends (score = 0). Total = 6 + 0 = 6.
   • Split at 1: left = [6,2] (sum=8), right = [3,4,5,5] (sum=17). 8 < 17, continue on left, score = 8 + dp(0,1). dp(0,1) will split [6,2], and so on.
   • Split at 2: left = [6,2,3] (sum=11), right = [4,5,5] (sum=14). 11 < 14, continue on left, score = 11 + dp(0,2).
   • Split at 3: left = [6,2,3,4] (sum=15), right = [5,5] (sum=10). 15 > 10, continue on right, score = 10 + dp(4,5).
   • Split at 4: left = [6,2,3,4,5] (sum=20), right = [5] (sum=5). 20 > 5, continue on right, score = 5 + dp(5,5).
3. For each split, recursively calculate the best possible score for the chosen part, and pick the maximum among all options.
4. Memoization ensures that subarrays like dp(0,2) or dp(4,5) are only computed once.
5. The final answer is the maximum score Alice can achieve for the full array.

Time and Space Complexity

Brute-force approach:

• Each split creates two recursive subproblems, leading to an exponential number of calls.
• Time complexity: O(2ⁿ) (not feasible for n up to 500).

• There are O(n²) possible subarrays.
• For each subarray, we try up to O(n) split points.
• Total time complexity: O(n³).
• Space complexity: O(n²) for the DP memoization table and O(n) for prefix sums.

For n = 500, this is efficient enough due to modern computation power and the use of memoization.

Summary

The Stone Game V problem is a classic example of using dynamic programming to optimize a recursive process with overlapping subproblems. By precomputing prefix sums and using memoization, we avoid redundant work and efficiently compute the maximum score Alice can obtain by always playing optimally. The approach is both systematic and scalable, turning an otherwise intractable brute-force solution into an elegant and performant one.

Code Implementation

from functools import lru_cache

class Solution:
    def stoneGameV(self, stoneValue):
        n = len(stoneValue)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + stoneValue[i]
        
        @lru_cache(None)
        def dp(l, r):
            if l == r:
                return 0
            res = 0
            for i in range(l, r):
                left = prefix[i+1] - prefix[l]
                right = prefix[r+1] - prefix[i+1]
                if left < right:
                    res = max(res, left + dp(l, i))
                elif left > right:
                    res = max(res, right + dp(i+1, r))
                else:
                    res = max(res, left + dp(l, i), right + dp(i+1, r))
            return res
        
        return dp(0, n-1)
    

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

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

import java.util.*;

class Solution {
    public int stoneGameV(int[] stoneValue) {
        int n = stoneValue.length;
        int[] prefix = new int[n+1];
        for (int i = 0; i < n; ++i)
            prefix[i+1] = prefix[i] + stoneValue[i];
        int[][] dp = new int[n][n];
        for (int[] row : dp)
            Arrays.fill(row, -1);
        return dfs(0, n-1, prefix, dp);
    }
    
    private int dfs(int l, int r, int[] prefix, int[][] dp) {
        if (l == r) return 0;
        if (dp[l][r] != -1) return dp[l][r];
        int res = 0;
        for (int i = l; i < r; ++i) {
            int left = prefix[i+1] - prefix[l];
            int right = prefix[r+1] - prefix[i+1];
            if (left < right)
                res = Math.max(res, left + dfs(l, i, prefix, dp));
            else if (left > right)
                res = Math.max(res, right + dfs(i+1, r, prefix, dp));
            else
                res = Math.max(res, Math.max(left + dfs(l, i, prefix, dp), right + dfs(i+1, r, prefix, dp)));
        }
        dp[l][r] = res;
        return res;
    }
}
    

var stoneGameV = function(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 dp = Array.from({length: n}, () => Array(n).fill(-1));
    
    function dfs(l, r) {
        if (l === r) return 0;
        if (dp[l][r] !== -1) return dp[l][r];
        let res = 0;
        for (let i = l; i < r; ++i) {
            let left = prefix[i+1] - prefix[l];
            let right = prefix[r+1] - prefix[i+1];
            if (left < right)
                res = Math.max(res, left + dfs(l, i));
            else if (left > right)
                res = Math.max(res, right + dfs(i+1, r));
            else
                res = Math.max(res, left + dfs(l, i), right + dfs(i+1, r));
        }
        dp[l][r] = res;
        return res;
    }
    return dfs(0, n-1);
};