Stone Game VIII

1
2
3
4
5
6
7
8
9

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        for i in range(1, n):
            stones[i] += stones[i - 1] # now stones[i] is the prefix sum
        dp = stones[-1] # dp[N - 2] = prefix[N - 1]
        for i in range(n - 2, 0, -1):
            dp = max(dp, stones[i] - dp) # dp[i - 1] = max(dp[i], stones[i] - dp[i])
        return dp # dp[0]

10 Prerequisite LeetCode Problems

“1872. Stone Game VIII” is a dynamic programming problem with a twist. Here are 10 problems as good preparation:

  1. 53. Maximum Subarray: Basic problem for understanding dynamic programming.

  2. 121. Best Time to Buy and Sell Stock: Here, you are required to maximize the profit which is an essential dynamic programming concept.

  3. 70. Climbing Stairs: A simple and fundamental problem that introduces dynamic programming.

  4. 198. House Robber: A classic problem where dynamic programming is used to maximize the amount robbed.

  5. 1143. Longest Common Subsequence: The problem introduces the idea of subsequence which is useful for the stone game problem.

  6. 300. Longest Increasing Subsequence: This problem further strengthens the concept of subsequence.

  7. 1043. Partition Array for Maximum Sum: This problem requires you to partition an array to maximize the sum, which is a helpful concept for the stone game problem.

  8. 213. House Robber II: An extension of the house robber problem which introduces more complex constraints.

  9. 221. Maximal Square: This problem helps you understand how to apply dynamic programming in two dimensions.

  10. 647. Palindromic Substrings: This problem introduces the idea of substring, which is helpful to understand the idea of subarrays required in the stone game problem.

These cover dynamic programming and handling arrays, which will be helpful in solving the “1872. Stone Game VIII” problem.

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player’s turn, while the number of stones is more than one, they will do the following:

Choose an integer x > 1, and remove the leftmost x stones from the row. Add the sum of the removed stones’ values to the player’s score. Place a new stone, whose value is equal to that sum, on the left side of the row. The game stops when only one stone is left in the row.

The score difference between Alice and Bob is (Alice’s score - Bob’s score). Alice’s goal is to maximize the score difference, and Bob’s goal is the minimize the score difference.

Given an integer array stones of length n where stones[i] represents the value of the ith stone from the left, return the score difference between Alice and Bob if they both play optimally.

Example 1:

Input: stones = [-1,2,-3,4,-5] Output: 5 Explanation:

  • Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of value 2 on the left. stones = [2,-5].
  • Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on the left. stones = [-3]. The difference between their scores is 2 - (-3) = 5.

Example 2:

Input: stones = [7,-6,5,10,5,-2,-6] Output: 13 Explanation:

  • Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a stone of value 13 on the left. stones = [13]. The difference between their scores is 13 - 0 = 13.

Example 3:

Input: stones = [-10,-12] Output: -22 Explanation:

  • Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her score and places a stone of value -22 on the left. stones = [-22]. The difference between their scores is (-22) - 0 = -22.

Constraints:

n == stones.length 2 <= n <= 105 -104 <= stones[i] <= 104