1563. Stone Game V Solution & Explanation

The problem

There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice's score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.

The game ends when there is only one stone remaining. Alice's is initially zero.

Return the maximum score that Alice can obtain.

Example 1:

Input: stoneValue = [6,2,3,4,5,5]
Output: 18
Explanation: In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice's score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice's score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.

Example 2:

Input: stoneValue = [7,7,7,7,7,7,7]
Output: 28

Example 3:

Input: stoneValue = [4]
Output: 0

Constraints:

1 <= stoneValue.length <= 500
1 <= stoneValue[i] <= 10⁶

Approach overview

Problem Overview: You are given an array where each value represents stones in a pile. At every step you split the array into two non-empty parts. The player only keeps the side with the smaller sum (or either if equal) and gains that sum as score. The goal is to maximize the total score after repeatedly splitting until one element remains.

Approach 1: Dynamic Programming with Prefix Sums (O(n^3) time, O(n^2) space)

The straightforward strategy models the problem using dynamic programming. Define dp[i][j] as the maximum score obtainable from the subarray stoneValue[i..j]. For every interval, iterate over all possible split points k. Use a prefix sum array to compute leftSum and rightSum in O(1). If leftSum < rightSum, you must keep the left side and add leftSum + dp[i][k]. If leftSum > rightSum, keep the right side and add rightSum + dp[k+1][j]. When both sums are equal, take the maximum of both options. Because every interval tries all split points, the runtime becomes O(n^3) with O(n^2) memory for the DP table.

This approach relies heavily on fast subarray sum computation using prefix sums over the array. It is conceptually simple and mirrors the game rules directly, making it a reliable baseline solution.

Approach 2: Optimized Dynamic Programming with Recursive Memoization (O(n^2) time, O(n^2) space)

You can reduce redundant work by combining recursion with memoization and pruning unnecessary splits. Use a recursive function dfs(l, r) that returns the best score for the interval. Prefix sums again provide O(1) range sum queries. During the split iteration, observe that once the left sum exceeds the right sum (or vice versa), future splits only make the imbalance larger. This allows pruning or skipping portions of the search space.

Memoize results for each pair (l, r) so every subproblem is computed once. With careful pruning and reuse of intermediate values, the algorithm effectively processes about O(n^2) states and near O(n) transitions per interval on average, giving roughly O(n^2) practical complexity. This technique mixes dynamic programming with recursive state exploration common in game theory problems.

Recommended for interviews: Start by explaining the interval DP idea with prefix sums. That demonstrates understanding of subproblem structure and state transitions. Interviewers usually expect the DP formulation first. The optimized memoized approach shows deeper insight into pruning and state reuse, which is valuable when discussing performance improvements.

Approach 1: Dynamic Programming with Prefix Sums

This approach uses dynamic programming with prefix sums to efficiently calculate the score for partitions. The prefix sum allows quick calculation of any subarray sum, which is key to determining the optimal split at each step. By storing the maximum score possible starting at each index in a dp array, we can ensure that at each partition step, we choose the path that leads to the highest potential score.

Python

def stoneGameV(stoneValue):
    n = len(stoneValue)
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i]
    dp = [0] * (n + 1)
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                left = prefix_sum[k + 1] - prefix_sum[i]
                right = prefix_sum[j + 1] - prefix_sum[k + 1]
                if left < right:
                    dp[i] = max(dp[i], left + dp[k + 1])
                elif left > right:
                    dp[i] = max(dp[i], right + dp[i])
                else:
                    dp[i] = max(dp[i], left + dp[k + 1], right + dp[i])
    return dp[0]

Java

class Solution {
    public int stoneGameV(int[] stoneValue) {
        int n = stoneValue.length;
        int[] prefix_sum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i];
        }
        int[] dp = new int[n + 1];
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                for (int k = i; k < j; k++) {
                    int left = prefix_sum[k + 1] - prefix_sum[i];
                    int right = prefix_sum[j + 1] - prefix_sum[k + 1];
                    if (left < right) {
                        dp[i] = Math.max(dp[i], left + dp[k + 1]);
                    } else if (left > right) {
                        dp[i] = Math.max(dp[i], right + dp[i]);
                    } else {
                        dp[i] = Math.max(dp[i], left + dp[k + 1], right + dp[i]);
                    }
                }
            }
        }
        return dp[0];
    }
}

C++

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

int stoneGameV(vector<int>& stoneValue) {
    int n = stoneValue.size();
    vector<int> prefix_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i];
    }
    vector<int> dp(n + 1, 0);
    for (int length = 2; length <= n; ++length) {
        for (int i = 0; i <= n - length; ++i) {
            int j = i + length - 1;
            for (int k = i; k < j; ++k) {
                int left = prefix_sum[k + 1] - prefix_sum[i];
                int right = prefix_sum[j + 1] - prefix_sum[k + 1];
                if (left < right) {
                    dp[i] = max(dp[i], left + dp[k + 1]);
                } else if (left > right) {
                    dp[i] = max(dp[i], right + dp[i]);
                } else {
                    dp[i] = max(dp[i], left + dp[k + 1], right + dp[i]);
                }
            }
        }
    }
    return dp[0];
}

JavaScript

function stoneGameV(stoneValue) {
    const n = stoneValue.length;
    const prefix_sum = Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i];
    }
    const dp = Array(n + 1).fill(0);
    for (let length = 2; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            let j = i + length - 1;
            for (let k = i; k < j; k++) {
                const left = prefix_sum[k + 1] - prefix_sum[i];
                const right = prefix_sum[j + 1] - prefix_sum[k + 1];
                if (left < right) {
                    dp[i] = Math.max(dp[i], left + dp[k + 1]);
                } else if (left > right) {
                    dp[i] = Math.max(dp[i], right + dp[i]);
                } else {
                    dp[i] = Math.max(dp[i], left + dp[k + 1], right + dp[i]);
                }
            }
        }
    }
    return dp[0];
}

#include <stdio.h>
#include <string.h>
int stoneGameV(int* stoneValue, int stoneValueSize) {
    int prefix_sum[stoneValueSize + 1];
    memset(prefix_sum, 0, sizeof(prefix_sum));
    for(int i = 0; i < stoneValueSize; i++) {
        prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i];
    }
    int dp[stoneValueSize + 1];
    memset(dp, 0, sizeof(dp));
    for(int length = 2; length <= stoneValueSize; length++) {
        for(int i = 0; i <= stoneValueSize - length; i++) {
            int j = i + length - 1;
            for(int k = i; k < j; k++) {
                int left = prefix_sum[k + 1] - prefix_sum[i];
                int right = prefix_sum[j + 1] - prefix_sum[k + 1];
                if (left < right) {
                    dp[i] = dp[i] > left + dp[k + 1] ? dp[i] : left + dp[k + 1];
                } else if (left > right) {
                    dp[i] = dp[i] > right + dp[i] ? dp[i] : right + dp[i];
                } else {
                    dp[i] = dp[i] > left + dp[k + 1] ? dp[i] : left + dp[k + 1];
                    dp[i] = dp[i] > right + dp[i] ? dp[i] : right + dp[i];
                }
            }
        }
    }
    return dp[0];
}

public class Solution {
    public int StoneGameV(int[] stoneValue) {
        int n = stoneValue.Length;
        int[] prefix_sum = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i];
        }
        int[] dp = new int[n + 1];
        for (int length = 2; length <= n; ++length) {
            for (int i = 0; i <= n - length; ++i) {
                int j = i + length - 1;
                for (int k = i; k < j; ++k) {
                    int left = prefix_sum[k + 1] - prefix_sum[i];
                    int right = prefix_sum[j + 1] - prefix_sum[k + 1];
                    if (left < right) {
                        dp[i] = Math.Max(dp[i], left + dp[k + 1]);
                    } else if (left > right) {
                        dp[i] = Math.Max(dp[i], right + dp[i]);
                    } else {
                        dp[i] = Math.Max(dp[i], Math.Max(left + dp[k + 1], right + dp[i]));
                    }
                }
            }
        }
        return dp[0];
    }
}

The solution starts by computing the prefix sums for the input array, which helps in calculating subarray sums efficiently. Then, it uses a dynamic programming array, `dp`, where `dp[i]` represents the maximum score Alice can achieve starting from the `i`-th stone. The nested loops attempt each possible partitioning position `k` and compute scores of the left and right segments. Based on the comparison, it updates `dp` with the optimal choice. The time complexity of this approach is O(n^3) due to the nested loops for both partitioning positions and interval lengths.

Complexity

Time Complexity: O(n^3)
Space Complexity: O(n)

Try this approach in the editor

Approach 2: Optimized Dynamic Programming with Recursive Memoization

This approach optimizes the dynamic programming strategy by incorporating recursive memoization. The recursive function breaks the stones into smaller subproblems and stores the computed results in a memoization table. This reduces redundant computations for overlapping subproblems.

Python

def stoneGameV(stoneValue):
    def dfs(l, r):
        if l == r:
            return 0
        if memo[l][r] != -1:
            return memo[l][r]
        max_score = 0
        for k in range(l, r):
            left = prefix_sum[k + 1] - prefix_sum[l]
            right = prefix_sum[r + 1] - prefix_sum[k + 1]
            if left < right:
                max_score = max(max_score, left + dfs(l, k))
            elif left > right:
                max_score = max(max_score, right + dfs(k + 1, r))
            else:
                max_score = max(max_score, left + dfs(l, k), right + dfs(k + 1, r))
        memo[l][r] = max_score
        return max_score

    n = len(stoneValue)
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i]
    memo = [[-1] * n for _ in range(n)]
    return dfs(0, n - 1)

Java

class Solution {
    private int dfs(int l, int r, int[][] memo, int[] prefix_sum) {
        if (l == r)
            return 0;
        if (memo[l][r] != -1)
            return memo[l][r];
        int max_score = 0;
        for (int k = l; k < r; ++k) {
            int left = prefix_sum[k + 1] - prefix_sum[l];
            int right = prefix_sum[r + 1] - prefix_sum[k + 1];
            if (left < right) {
                max_score = Math.max(max_score, left + dfs(l, k, memo, prefix_sum));
            } else if (left > right) {
                max_score = Math.max(max_score, right + dfs(k + 1, r, memo, prefix_sum));
            } else {
                max_score = Math.max(max_score, Math.max(left + dfs(l, k, memo, prefix_sum), right + dfs(k + 1, r, memo, prefix_sum)));
            }
        }
        return memo[l][r] = max_score;
    }

    public int stoneGameV(int[] stoneValue) {
        int n = stoneValue.length;
        int[] prefix_sum = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i];
        }
        int[][] memo = new int[n][n];
        for (int[] row : memo)
            Arrays.fill(row, -1);
        return dfs(0, n - 1, memo, prefix_sum);
    }
}

C++

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

int dfs(int l, int r, vector<vector<int>>& memo, vector<int>& prefix_sum) {
    if (l == r)
        return 0;
    if (memo[l][r] != -1)
        return memo[l][r];
    int max_score = 0;
    for (int k = l; k < r; ++k) {
        int left = prefix_sum[k + 1] - prefix_sum[l];
        int right = prefix_sum[r + 1] - prefix_sum[k + 1];
        if (left < right) 
            max_score = max(max_score, left + dfs(l, k, memo, prefix_sum));
        else if (left > right) 
            max_score = max(max_score, right + dfs(k + 1, r, memo, prefix_sum));
        else 
            max_score = max({max_score, left + dfs(l, k, memo, prefix_sum), right + dfs(k + 1, r, memo, prefix_sum)});
    }
    return memo[l][r] = max_score;
}

int stoneGameV(vector<int>& stoneValue) {
    int n = stoneValue.size();
    vector<int> prefix_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i];
    }
    vector<vector<int>> memo(n, vector<int>(n, -1));
    return dfs(0, n - 1, memo, prefix_sum);
}

JavaScript

function stoneGameV(stoneValue) {
    function dfs(l, r) {
        if (l === r) return 0;
        if (memo[l][r] !== -1) return memo[l][r];
        let max_score = 0;
        for (let k = l; k < r; k++) {
            const left = prefix_sum[k + 1] - prefix_sum[l];
            const right = prefix_sum[r + 1] - prefix_sum[k + 1];
            if (left < right) {
                max_score = Math.max(max_score, left + dfs(l, k));
            } else if (left > right) {
                max_score = Math.max(max_score, right + dfs(k + 1, r));
            } else {
                max_score = Math.max(max_score, left + dfs(l, k), right + dfs(k + 1, r));
            }
        }
        return memo[l][r] = max_score;
    }

    const n = stoneValue.length;
    const prefix_sum = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i];
    }
    const memo = Array.from({ length: n }, () => Array(n).fill(-1));
    return dfs(0, n - 1);
}

#include <stdio.h>
#include <string.h>

int dfs(int l, int r, int memo[][500], int* prefix_sum) {
    if (l == r) return 0;
    if (memo[l][r] != -1) return memo[l][r];
    int max_score = 0;
    for (int k = l; k < r; ++k) {
        int left = prefix_sum[k + 1] - prefix_sum[l];
        int right = prefix_sum[r + 1] - prefix_sum[k + 1];
        if (left < right)
            max_score = max_score > left + dfs(l, k, memo, prefix_sum) ? max_score : left + dfs(l, k, memo, prefix_sum);
        else if (left > right)
            max_score = max_score > right + dfs(k + 1, r, memo, prefix_sum) ? max_score : right + dfs(k + 1, r, memo, prefix_sum);
        else {
            int temp = left + dfs(l, k, memo, prefix_sum);
            max_score = max_score > temp ? max_score : temp;
            temp = right + dfs(k + 1, r, memo, prefix_sum);
            max_score = max_score > temp ? max_score : temp;
        }
    }
    return memo[l][r] = max_score;
}

int stoneGameV(int* stoneValue, int stoneValueSize) {
    int prefix_sum[stoneValueSize + 1];
    memset(prefix_sum, 0, sizeof(prefix_sum));
    for (int i = 0; i < stoneValueSize; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i];
    }
    int memo[500][500];
    memset(memo, -1, sizeof(memo));
    return dfs(0, stoneValueSize - 1, memo, prefix_sum);
}

public class Solution {
    public int StoneGameV(int[] stoneValue) {
        int n = stoneValue.Length;
        int[] prefix_sum = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i];
        }
        int[,] memo = new int[n, n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                memo[i, j] = -1;

        return dfs(0, n - 1, memo, prefix_sum);
    }

    private int dfs(int l, int r, int[,] memo, int[] prefix_sum) {
        if (l == r) return 0;
        if (memo[l, r] != -1) return memo[l, r];
        int max_score = 0;
        for (int k = l; k < r; ++k) {
            int left = prefix_sum[k + 1] - prefix_sum[l];
            int right = prefix_sum[r + 1] - prefix_sum[k + 1];
            if (left < right) {
                max_score = Math.Max(max_score, left + dfs(l, k, memo, prefix_sum));
            } else if (left > right) {
                max_score = Math.Max(max_score, right + dfs(k + 1, r, memo, prefix_sum));
            } else {
                max_score = Math.Max(max_score, Math.Max(left + dfs(l, k, memo, prefix_sum), right + dfs(k + 1, r, memo, prefix_sum)));
            }
        }
        return memo[l, r] = max_score;
    }
}

This solution enhances the dynamic programming technique by utilizing a recursive function `dfs` which calculates the optimal score for a segment of stones from the `l`-th to the `r`-th. The results of these recursive calls are cached in a `memo`ization table to avoid recalculating scores for previously solved subproblems. The recursive decomposition reduces unnecessary O(n^3) evaluations.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n^2)

Try this approach in the editor

Approach 3: Memoization + Pruning

First, we preprocess the prefix sum array s, where s[i] represents the sum of the first i elements of the array stoneValue.

Next, we design a function dfs(i, j), which represents the maximum score Alice can get from the stones in the subarray stoneValue within the index range [i, j]. The answer is dfs(0, n - 1).

The calculation process of the function dfs(i, j) is as follows:

If i geq j, it means there is only one stone left, and Alice cannot split it, so return 0.
Otherwise, we enumerate the split point k, i.e., i leq k < j, splitting the stones in the subarray stoneValue within the index range [i, j] into two parts: [i, k] and [k + 1, j]. We calculate a and b, which represent the total sum of the stones in the two parts, respectively. Then we calculate dfs(i, k) and dfs(k + 1, j), and update the answer.

Note that if a < b and ans geq a times 2, this enumeration can be skipped; if a > b and ans geq b times 2, all subsequent enumerations can be skipped, and the loop can be exited directly.

Finally, we return the answer.

To avoid repeated calculations, we can use memoization and pruning to optimize the enumeration efficiency.

The time complexity is O(n^3), and the space complexity is O(n^2). Here, n is the length of the array stoneValue.

TypeScript

function stoneGameV(stoneValue: number[]): number {
    const n = stoneValue.length;
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        s[i + 1] = s[i] + stoneValue[i];
    }
    const f: number[][] = Array.from({ length: n }, () => Array(n).fill(-1));

    const dfs = (i: number, j: number): number => {
        if (i >= j) {
            return 0;
        }
        if (f[i][j] !== -1) {
            return f[i][j];
        }
        let [ans, l, r] = [0, 0, s[j + 1] - s[i]];
        for (let k = i; k < j; ++k) {
            l += stoneValue[k];
            r -= stoneValue[k];
            if (l < r) {
                if (ans > l * 2) {
                    continue;
                }
                ans = Math.max(ans, l + dfs(i, k));
            } else if (l > r) {
                if (ans > r * 2) {
                    break;
                }
                ans = Math.max(ans, r + dfs(k + 1, j));
            } else {
                ans = Math.max(ans, l + dfs(i, k), r + dfs(k + 1, j));
            }
        }
        return (f[i][j] = ans);
    };

    return dfs(0, n - 1);
}

func stoneGameV(stoneValue []int) int {
	n := len(stoneValue)
	s := make([]int, n+1)
	for i, x := range stoneValue {
		s[i+1] = s[i] + x
	}
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if i >= j {
			return 0
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		ans, l, r := 0, 0, s[j+1]-s[i]
		for k := i; k < j; k++ {
			l += stoneValue[k]
			r -= stoneValue[k]
			if l < r {
				if ans > l*2 {
					continue
				}
				ans = max(ans, dfs(i, k)+l)
			} else if l > r {
				if ans > r*2 {
					break
				}
				ans = max(ans, dfs(k+1, j)+r)
			} else {
				ans = max(ans, max(dfs(i, k), dfs(k+1, j))+l)
			}
		}
		f[i][j] = ans
		return ans
	}
	return dfs(0, n-1)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with Prefix Sums	Time Complexity: O(n^3) Space Complexity: O(n)
Optimized Dynamic Programming with Recursive Memoization	Time Complexity: O(n^2) Space Complexity: O(n^2)
Memoization + Pruning	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with Prefix Sums	O(n^3)	O(n^2)	Baseline solution that clearly models all splits. Good for understanding interval DP.
Optimized DP with Recursive Memoization	O(n^2)	O(n^2)	Preferred for larger inputs. Uses pruning and memoization to avoid redundant split evaluations.

Frequently asked questions

Is Stone Game V easy or hard?

Stone Game V is classified as a Hard problem on LeetCode. It requires recognizing an interval dynamic programming pattern, handling conditional transitions based on subarray sums, and optimizing repeated computations.

Stone Game V Python/Java solution

The typical implementation builds a prefix sum array and then applies either bottom-up interval DP or a top-down recursive memoization function. The same algorithm works across Python, Java, C++, and JavaScript with only syntax differences.

How to solve Stone Game V in O(n^2)?

Use recursive dynamic programming with memoization and prefix sums. The recursion processes each interval once and prunes split positions when the running sums become strictly larger on one side. This significantly reduces the number of evaluated transitions compared to the naive O(n^3) DP.

What is the best approach for Stone Game V?

The most effective approach uses dynamic programming with prefix sums and memoization. Define dp[i][j] as the maximum score for the subarray and try all split points while comparing left and right sums. Prefix sums allow constant-time range sum queries, and memoization ensures each interval is computed once.

Is Stone Game V asked at Google/Amazon/Meta?

Stone Game–style problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test interval dynamic programming, prefix sums, and reasoning about optimal decisions in competitive scenarios.

What data structure is used in Stone Game V?

The main structures are arrays for the input and prefix sums, along with a 2D DP table or memoization cache. These structures enable efficient subarray sum calculation and storage of optimal results for each interval.

What is the time complexity of Stone Game V?

The classic interval dynamic programming solution runs in O(n^3) time and O(n^2) space because every subarray tries all possible split points. With pruning and recursive memoization, the practical complexity improves to around O(n^2) while still storing O(n^2) states.

Stone Game V solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Prefix Sums

Approach 2: Optimized Dynamic Programming with Recursive Memoization

Approach 3: Memoization + Pruning

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Stone Game V solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Prefix Sums

Approach 2: Optimized Dynamic Programming with Recursive Memoization

Approach 3: Memoization + Pruning

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems