{x}
blog image

Stone Game V

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] <= 106

Solution Explanation: Stone Game V

This problem presents a variation of the classic Stone Game, introducing the concept of dividing stones and maximizing Alice's score. A dynamic programming approach with memoization and pruning is highly effective for solving this.

Core Idea:

The solution uses a recursive function dfs(i, j) to find the maximum score Alice can achieve for a subarray of stones from index i to j. The base case is when i >= j (single stone left), returning 0. The recursive step involves trying all possible splits k ( i <= k < j), calculating the sums of the two resulting subarrays (a and b), and recursively calling dfs on the remaining subarray. Alice's score is updated based on the smaller of the two sums after Bob discards the larger one.

Optimization Techniques:

  • Memoization: The dfs function utilizes memoization (caching previously computed results) to avoid redundant calculations, significantly improving efficiency. This is implemented using a 2D array f (or a dictionary/map in Python) to store the results of dfs(i, j).

  • Prefix Sum: A prefix sum array s is used to efficiently calculate the sum of stones in any subarray in O(1) time. s[i] stores the sum of stoneValue from index 0 to i-1.

  • Pruning: To further optimize the search, pruning is applied. If the current split results in subarray sums a and b where a < b, and the current maximum score ans is already at least twice a, then there's no need to continue exploring this branch because Alice's score from this split cannot be better than the current ans. Similarly, if a > b, and ans is at least twice b, this branch is pruned.

Time and Space Complexity:

  • Time Complexity: O(n³). The triple nested loop (implicit in the recursive calls) dominates. However, memoization and pruning greatly reduce the actual number of computations. Without pruning, it would be strictly O(n³).

  • Space Complexity: O(n²). This is due to the memoization table f which stores results for all possible subarrays. The prefix sum array s only uses linear space, O(n).

Code in Different Languages:

The provided code demonstrates the solution in Python, Java, C++, Go, and TypeScript. All implementations follow the same underlying logic, utilizing memoization, prefix sums, and pruning for optimal performance. The key differences lie in syntax and data structure choices specific to each language. For instance, Python uses @cache decorator for memoization, while Java and C++ use explicit Integer[][] and int[][] arrays respectively. Note that the max function is often helper function within the code to take care of finding the maximum of two numbers

Example Walkthrough (Python):

Let's trace a simplified example: stoneValue = [2, 4, 6].

  1. dfs(0, 2) is called.
  2. The loop iterates through k = 0, 1.
  3. When k = 0, l = 2, r = 10. The condition l < r is met, and dfs(0, 0) (which returns 0) is recursively called. ans becomes max(0, 2 + 0) = 2.
  4. When k = 1, l = 6, r = 6. The condition l == r is met. dfs(0, 1) and dfs(2, 2) are recursively called. Eventually, ans will be updated to the maximum of the scores obtained from the recursive calls. The pruning condition would also influence this step,potentially reducing the number of calls needed.

The final result will be the maximum score Alice can obtain. The memoization ensures that dfs(0,1) and dfs(1,2) (and possibly others) are only computed once.