1563. Stone Game V


Problem Description

In the "Stone Game V" problem, you are given a row of stones with each stone having an associated value. The objective is for the player, Alice, to score as high as possible through a series of rounds. During each round, Alice divides the row of stones into two non-empty parts. Then, Bob, another player, calculates the sum of values for each part. Bob discards the part with the higher sum, and Alice's score is increased by the sum of the remaining part. If both parts have an equal sum, Alice gets to decide which part to discard. This process repeats until only one stone remains. Alice's score starts at zero, and the goal is to find the maximum score Alice can achieve by the end of the game.

Intuition

The intuition behind the solution is to recognize that we are dealing with an optimization problem with overlapping subproblems and optimal substructure, meaning the problem can be effectively solved using dynamic programming. More specifically, since Alice can make different choices leading to different outcomes, we explore different ways of splitting the stones, always considering the best score Alice can get from any given point.

Memoization (caching the results of expensive function calls) is applied to ensure we do not compute the same state more than once. The problem is recursive in nature - for every split Alice makes, there are subsequently different potential splits that can be made thereafter. Therefore, we define a recursive function dfs(i, j), which represents the maximum score Alice can achieve from stones in the range stoneValue[i] to stoneValue[j].

This function compares the sum of values in the left and right partitions of the current range, always trying to maximize the score obtained by Alice. If the left partition has a lesser sum than the right, we only consider the left partition for further recursive calls (since Bob would discard the right). Conversely, if the right partition has a lesser sum, we consider the right partition for recursion. If both partitions have equal sums, we consider both partitions to find the maximum score. We use an accumulated sum array s to efficiently calculate the sum of stones for each partition.

The solution uses top-down dynamic programming strategy to break down the game into manageable states (represented by the recursive function dfs) and relies on a memoization technique to cache answers to subproblems. By exploring all possible splits and choosing the optimal ones at each step, the function calculates the maximum score that Alice can gain.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The implementation uses dynamic programming with memoization to optimize the recursive search. The key elements of the solution are:

  • Memoization: The dfs function is decorated with Python's @cache feature, which memoizes the results. It stores the output of the function for each unique set of arguments (i, j) to ensure we do not repeat computations. This is essential for reducing the problem's complexity from exponential to polynomial time.

  • Recursive Function (dfs): The dfs(i, j) function calculates the maximum score from the subarray of stoneValue starting at index i and ending at index j. It uses recursion to try each possible division of the array into left and right parts and finds the optimal score that can be achieved from that point onwards.

  • Accumulated Sum Array (s): An accumulated sum array s is created using Python's accumulate function with initial=0. This array helps in efficiently calculating the sum of values in any subarray stoneValue[i:j+1] by simply calculating s[j+1] - s[i] without needing to sum the elements each time.

  • Optimization Logic: As we divide the array and calculate the sum a of the left part, we also calculate the sum b of the right part as s[j + 1] - s[i] - a. Depending on whether a is less than, greater than, or equal to b, we make recursive calls for the next round accordingly:

    • If a < b, we only need to consider the maximum score obtained from the left part (dfs(i, k)) because Bob would throw away the right part.
    • If a > b, we only need to consider the maximum score obtained from the right part (dfs(k + 1, j)) for similar reasons.
    • If a == b, Alice has the chance to choose either part, so we calculate and compare the scores for both possible decisions, dfs(i, k) and dfs(k + 1, j), and take the one which gives the maximum score.
  • Pruning: To further optimize, the implementation includes pruning steps where it avoids unnecessary recursive calls. If ans (current max score in our range) is already greater than or equal to twice the sum of a part, then we know exploring that part further won't yield a better outcome and we can skip making those recursive calls.

By applying these techniques, the solution efficiently explores all possibilities while avoiding redundant computations, leading to the maximum score Alice can achieve in the Stone Game V.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach for the Stone Game V problem, let's consider a small example where the stoneValue array is [6, 2, 3, 4]. Alice is trying to maximize her score by choosing the optimal places to split the array of stones.

  1. We initialize the accumulated sum array s as [0, 6, 8, 11, 15], which includes an initial zero for simplifying the sum calculations.

  2. We start by calling the recursive function dfs(0, 3) to calculate the maximum score Alice can obtain with the full array of stones from index 0 to 3.

  3. Inside dfs(0, 3), we try splitting the array into two parts at different positions:

    • Split between 6 and 2: a = s[1] - s[0] = 6, b = s[4] - s[1] = 9
      • Since a < b, the maximum score for this division would be the result of dfs(0, 0) which is 6 (because Bob would throw away the part that includes [2, 3, 4]).
    • Split between 2 and 3: a = s[2] - s[0] = 8, b = s[4] - s[2] = 7
      • Since a > b, the maximum score for this division would be the result of dfs(2, 3) which is 7 (because Bob would throw away the part that includes [6, 2]).
    • Split between 3 and 4: a = s[3] - s[0] = 11, b = s[4] - s[3] = 4
      • Since a > b, the maximum score for this division would be the result of dfs(3, 3) which is 4 (because Bob would throw away the part that includes [6, 2, 3]).
  4. Since dfs(0, 0), dfs(2, 3), and dfs(3, 3) do not involve any further splits (single element arrays), they simply return their element's value as the maximum score.

  5. We compare the possible outcomes of each split for dfs(0, 3):

    • The result of dfs(0, 0) is 6.
    • The result of dfs(2, 3) is 7.
    • The result of dfs(3, 3) is 4.
  6. The maximum score that Alice can achieve is the maximum of the results above, which is 7, achieved by splitting the array between indexes [6, 2] and [3, 4].

  7. By caching these results in our memoization structure, we avoid recalculating dfs(0, 0), dfs(2, 3), and dfs(3, 3) in future iterations.

  8. The memoization ensures that subsequent calls to dfs with the same (i, j) arguments will not repeat the calculation but will retrieve the result from the cache.

By following this approach for all possible splits and recursing as needed, we can find that the maximum score Alice can achieve with the stoneValue array [6, 2, 3, 4] is 7.

Solution Implementation

1from functools import lru_cache
2from itertools import accumulate
3from typing import List
4
5class Solution:
6    def stoneGameV(self, stone_values: List[int]) -> int:
7        # Using memoization to optimize recursive calls
8        @lru_cache(None)
9        def dfs(left_index, right_index):
10            # Base case: when there's only one stone, no score can be obtained
11            if left_index == right_index:
12                return 0
13
14            max_score = 0
15            left_sum = 0
16
17            # Try splitting the array at different points to maximize the score
18            for split_index in range(left_index, right_index):
19                # Sum of values on the left of the split point
20                left_sum += stone_values[split_index]
21                # Sum of values on the right of the split point
22                right_sum = prefix_sums[right_index + 1] - prefix_sums[left_index] - left_sum
23
24                # Compare sums to decide which side to choose
25                if left_sum < right_sum:
26                    # If the left sum is less, consider the left portion;
27                    # skip if not better than double the current max_score
28                    if max_score >= left_sum * 2:
29                        continue
30                    max_score = max(max_score, left_sum + dfs(left_index, split_index))
31                elif left_sum > right_sum:
32                    # If the right sum is less, consider the right portion;
33                    # stop splitting further right if not better than double the current max_score
34                    if max_score >= right_sum * 2:
35                        break
36                    max_score = max(max_score, right_sum + dfs(split_index + 1, right_index))
37                else:
38                    # If both are equal, consider both portions and take the maximum
39                    max_score = max(max_score, left_sum + dfs(left_index, split_index), right_sum + dfs(split_index + 1, right_index))
40
41            return max_score
42
43        # Compute prefix sums for stone_values to use later in splitting
44        prefix_sums = list(accumulate(stone_values, initial=0))
45
46        # Compute the maximum score by starting from the entire range
47        return dfs(0, len(stone_values) - 1)
48
49# Example usage:
50# stone_values = [6, 2, 3, 4, 5]
51# solution = Solution()
52# result = solution.stoneGameV(stone_values)
53# print(result)  # This will print the result of the stone game V for the given stone values.
54
1class Solution {
2    private int numStones; // Total number of stones
3    private int[] prefixSums; // Array to store prefix sums
4    private int[] stoneValues; // Array to store values of stones
5    private Integer[][] memo; // Memoization array to avoid repeated calculation
6
7    public int stoneGameV(int[] stoneValue) {
8        numStones = stoneValue.length;
9        this.stoneValues = stoneValue;
10        prefixSums = new int[numStones + 1]; // One additional space to include sum up to 0 
11      
12        // Pre-calculate prefix sums to enable fast range sum queries
13        for (int i = 1; i <= numStones; ++i) {
14            prefixSums[i] = prefixSums[i - 1] + stoneValue[i - 1];
15        }
16      
17        memo = new Integer[numStones][numStones]; // Initialize memoization matrix
18        return dfs(0, numStones - 1);
19    }
20
21    // Helper method to recursively find the maximum score using DFS and memoization
22    private int dfs(int left, int right) {
23        if (left == right) {
24            // Base case: when there is only one stone, score is 0
25            return 0;
26        }
27        if (memo[left][right] != null) {
28            // Return previously computed value if available to avoid repeat calculations
29            return memo[left][right];
30        }
31      
32        int maxScore = 0; // Store the maximum score found so far
33        int leftSum = 0; // Sum of the left partition
34
35        // Iterate over all possible partitions between left and right
36        for (int k = left; k < right; ++k) {
37            // Accumulate value of stones for the current partition
38            leftSum += stoneValues[k];
39            // Compute right partition sum
40            int rightSum = prefixSums[right + 1] - prefixSums[left] - leftSum;
41          
42            if (leftSum < rightSum) {
43                // If left partition has less sum, consider the left partition
44                if (maxScore >= leftSum * 2) {
45                    continue;
46                }
47                maxScore = Math.max(maxScore, leftSum + dfs(left, k));
48            } else if (leftSum > rightSum) {
49                // If right partition has less sum, consider the right partition
50                if (maxScore >= rightSum * 2) {
51                    break;
52                }
53                maxScore = Math.max(maxScore, rightSum + dfs(k + 1, right));
54            } else {
55                // If sums are equal, consider the maximum value from both partitions
56                maxScore = Math.max(maxScore, Math.max(leftSum + dfs(left, k), rightSum + dfs(k + 1, right)));
57            }
58        }
59        // Store the computed value in memo and return it
60        return memo[left][right] = maxScore;
61    }
62}
63
1#include <vector>
2#include <cstring>
3#include <functional>
4
5class Solution {
6public:
7    int stoneGameV(std::vector<int>& stoneValue) {
8        int n = stoneValue.size();
9        std::vector<int> prefixSum(n + 1, 0);
10        // Calculate the prefix sums for quick range sum queries.
11        for (int i = 1; i <= n; ++i) {
12            prefixSum[i] = prefixSum[i - 1] + stoneValue[i - 1];
13        }
14
15        // Initialize memoization table
16        std::vector<std::vector<int>> memo(n, std::vector<int>(n, 0));
17
18        // Define the DFS function for dynamic programming with memoization.
19        std::function<int(int, int)> dfs = [&](int left, int right) -> int {
20            // If the range consists of a single stone, no more score can be accrued.
21            if (left == right) {
22                return 0;
23            }
24            // If we have already computed the solution for this subrange, return the result.
25            if (memo[left][right]) {
26                return memo[left][right];
27            }
28            int maxScore = 0;
29            int leftSum = 0;
30            // Iterate through all possible partitions of the range
31            for (int k = left; k < right; ++k) {
32                leftSum += stoneValue[k];
33                int rightSum = prefixSum[right + 1] - prefixSum[left] - leftSum;
34                // Split into [left, k] and [k+1, right] and calculate recursively.
35                if (leftSum < rightSum) {
36                    maxScore = std::max(maxScore, leftSum + dfs(left, k));
37                } else if (leftSum > rightSum) {
38                    maxScore = std::max(maxScore, rightSum + dfs(k + 1, right));
39                } else {
40                    // If leftSum equals rightSum, calculate both and take the maximum.
41                    maxScore = std::max({maxScore, leftSum + dfs(left, k), rightSum + dfs(k + 1, right)});
42                }
43            }
44            // Store the result in the memoization table before returning.
45            return memo[left][right] = maxScore;
46        };
47
48        // Call the DFS function for the full range.
49        return dfs(0, n - 1);
50    }
51};
52
53// Example usage:
54// Solution sol;
55// std::vector<int> stoneValue = {6, 2, 3, 4, 5};
56// int result = sol.stoneGameV(stoneValue);
57
1function stoneGameV(stoneValue: number[]): number {
2    const n: number = stoneValue.length;
3    const prefixSum: number[] = new Array(n + 1).fill(0);
4    // Calculate the prefix sums for quick range sum queries
5    for (let i = 1; i <= n; ++i) {
6        prefixSum[i] = prefixSum[i - 1] + stoneValue[i - 1];
7    }
8
9    // Initialize memoization table
10    const memo: number[][] = new Array(n).fill(0).map(() => new Array(n).fill(0));
11
12    // Define the recursive function for dynamic programming with memoization
13    const dfs: (left: number, right: number) => number = (left, right) => {
14        // If the range consists of a single stone, no more score can be accrued
15        if (left === right) {
16            return 0;
17        }
18        // If we have already computed the solution for this subrange, return the result
19        if (memo[left][right]) {
20            return memo[left][right];
21        }
22        let maxScore = 0;
23        let leftSum = 0;
24        // Iterate through all possible partitions of the range
25        for (let k = left; k < right; ++k) {
26            leftSum += stoneValue[k];
27            const rightSum = prefixSum[right + 1] - prefixSum[k + 1];
28            // Split into [left, k] and [k+1, right] and calculate recursively
29            if (leftSum < rightSum) {
30                maxScore = Math.max(maxScore, leftSum + dfs(left, k));
31            } else if (leftSum > rightSum) {
32                maxScore = Math.max(maxScore, rightSum + dfs(k + 1, right));
33            } else {
34                // If leftSum equals rightSum, calculate both and take the maximum
35                maxScore = Math.max(maxScore, leftSum + dfs(left, k), rightSum + dfs(k + 1, right));
36            }
37        }
38        // Store the result in the memoization table before returning
39        memo[left][right] = maxScore;
40        return maxScore;
41    };
42
43    // Call the recursive function for the full range
44    return dfs(0, n - 1);
45}
46
47// Example usage:
48// const stoneValue: number[] = [6, 2, 3, 4, 5];
49// const result: number = stoneGameV(stoneValue);
50

Time and Space Complexity

Time Complexity

The time complexity of the dfs function is defined by the number of subproblems it needs to solve and the time it takes to solve each problem. Since the function uses memoization, each subproblem (defined by different (i, j) pairs where i and j are the indices of stoneValue) is only solved once. The number of subproblems that can be formed in a list of N stones is O(N^2) because there are N choices for where to start (i) and N choices for where to end (j), though in practice, it's less because i has to be less than j.

The function dfs itself does a single pass from i to j in each call. This means that for each subproblem, you have to do O(j-i) work to find the partition point k that gives the optimal score. In the worst case, this is O(N) work per subproblem. So if every (i, j) pair were considered and we did linear work on each, the time complexity of solving all subproblems would be O(N^3).

However, by using pruning (if-statements that use a running total to skip unnecessary work), the code ensures that it doesn't continue to look for a better partition once it's clear that no better partition is possible. This optimization makes it difficult to define an exact worst-case time complexity, as it's heavily input-dependent, but the use of memoization and pruning brings the expected time complexity down considerably in typical cases. Nonetheless, the upper bound in the absence of any pruning would still be O(N^3).

Space Complexity

The space complexity is determined by the size of the memoization cache and the call stack due to recursion. As noted above, there can be O(N^2) subproblems, so dfs can be called that many times in different contexts, and that many results can be stored. Thus, the memoization cache has a space complexity of O(N^2).

Recursion also consumes stack space. In the worst case, the dfs function might recurse N times before reaching a base case (when i equals j). Thus, the stack space used in the worst case is O(N).

Adding the space for the prefix sum array, which is O(N), the total space complexity becomes O(N^2) + O(N) + O(N), which simplifies to O(N^2) because in big-O notation, we focus on the term that grows fastest as N increases.

Therefore, the overall space complexity is O(N^2).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.