#1563

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Stone Game V

In Stone Game V, Alice divides stones into rows to maximize her score, using a dynamic programming approach to try all divisions.

array math dynamic programming game theory

Problem Statement

In the Stone Game V, you are given a row of stones, each with a value from the array stoneValue. Alice divides the row into two non-empty subarrays. Bob then discards the subarray with the higher sum, and Alice adds the sum of the remaining subarray to her score. If both subarrays have the same sum, Alice can choose which one to discard. The game continues until only one stone remains.

Alice's goal is to maximize her total score. The game starts with zero score, and she must strategically divide the array in every round to maximize the score at each step. The challenge lies in evaluating every possible division and determining the optimal sequence of moves using dynamic programming.

Examples

Example 1

Input: stoneValue = [6,2,3,4,5,5]

Output: 18

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 details omitted.

Example 3

Input: stoneValue = [4]

Output: 0

Example details omitted.

Constraints

1 <= stoneValue.length <= 500
1 <= stoneValue[i] <= 106

Solution Approach

State Transition Dynamic Programming

The solution relies on a dynamic programming approach where we maintain a state for each subarray of stones. At each step, we compute the optimal division of the array into two subarrays and update the score based on the possible outcomes. This allows us to efficiently determine the best possible score Alice can achieve for any given configuration of stones.

Iterate Through All Possible Divisions

To compute the optimal score, we need to evaluate all possible ways to split the stone row into two parts. This involves iterating through every valid partition and calculating the resulting scores. The maximum of these scores is then used to update the dynamic programming state.

Optimize With Precomputed Sums

Precomputing the cumulative sums of the stones helps to avoid recalculating the sum of each subarray multiple times. By using these sums, we can efficiently compute the score for any division of the array, speeding up the solution and ensuring the dynamic programming approach runs within the time limits.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depends on the approach used for dynamic programming. The solution requires iterating over all possible partitions, leading to a time complexity of O(n^2) where n is the length of the stoneValue array. Space complexity is also O(n^2) due to the storage of intermediate states in the dynamic programming table.

What Interviewers Usually Probe

Understanding of dynamic programming and state transitions is key.
Ability to break down the problem into smaller subproblems.
Efficient computation using precomputed sums is a strong signal.

Common Pitfalls or Variants

Common pitfalls

Failing to consider all possible divisions of the array.
Not optimizing the solution with precomputed sums, leading to inefficient code.
Overcomplicating the dynamic programming state, missing simpler solutions.

Follow-up variants

Consider variations where Alice's scoring method changes or where Bob's discard rule is different.
Solve with a greedy strategy or approximate solution to test how close it gets to the optimal solution.
Explore cases with larger arrays to see how the solution scales.

FAQ

What is the main approach to solving Stone Game V?

Stone Game V is best solved using state transition dynamic programming, where you evaluate all possible divisions of the stone row to maximize Alice's score.

Why do we need to evaluate all divisions in Stone Game V?

Each division leads to a different possible outcome, so evaluating all divisions ensures that we choose the optimal strategy for Alice to maximize her score.

How do I optimize my Stone Game V solution?

Optimize the solution by precomputing the cumulative sums of the stone array to speed up the calculation of scores for each possible division.

Can I use a greedy approach to solve Stone Game V?

A greedy approach may not always yield the optimal solution, as it does not guarantee evaluating all potential optimal divisions.

What are the common mistakes in solving Stone Game V?

Common mistakes include failing to evaluate all possible divisions, not optimizing with precomputed sums, and overcomplicating the dynamic programming state.

terminal

Solution

Solution 1: Memoization + Pruning

First, we preprocess the prefix sum array $\textit{s}$, where $\textit{s}[i]$ represents the sum of the first $i$ elements of the array $\textit{stoneValue}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

def max(a: int, b: int) -> int:
    return a if a > b else b


class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= j:
                return 0
            ans = l = 0
            r = s[j + 1] - s[i]
            for k in range(i, j):
                l += stoneValue[k]
                r -= stoneValue[k]
                if l < r:
                    if ans >= l * 2:
                        continue
                    ans = max(ans, l + dfs(i, k))
                elif l > r:
                    if ans >= r * 2:
                        break
                    ans = max(ans, r + dfs(k + 1, j))
                else:
                    ans = max(ans, max(l + dfs(i, k), r + dfs(k + 1, j)))
            return ans

        s = list(accumulate(stoneValue, initial=0))
        return dfs(0, len(stoneValue) - 1)

Continue Practicing

#1690 stone game vii #1406 stone game iii #1728 cat and mouse ii