Description

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, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones’ values in the row. The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score’s difference. Alice’s goal is to maximize the difference in the score.

Given an array of integers stones where stones[i] represents the value of the ith stone from the left, return the difference in Alice and Bob’s score if they both play optimally.

Example 1:

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

• Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
• Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
• Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
• Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
• Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = []. The score difference is 18 - 12 = 6. Example 2:

Input: stones = [7,90,5,1,100,10,10,2] Output: 122

Constraints:

n == stones.length 2 <= n <= 1000 1 <= stones[i] <= 1000

Solution

The first instinct I have is to use dynamic programming to solve this problem, since most optimal/minimum/maximum problem can be solved by dynamic programming. In order to use that, we need to find the state transfer function or recurrence relation. For a given stone subarray [i , j]. If we define the optimal difference be dp(i)(j), there are two situations. If Alice or Bob took i then the difference will be sum(i + 1, j) - dp(i + 1, j). The minus sign is important, since Alice - Bob’s score will be Bob - Alice’s score’s negative plus the score Alice will get during take stone i. Similar argument when Alice took stone j. The final answer will be the maximum between these two. So

dp[i][j] = max(sum[i + 1, j] - dp[i + 1][j], sum[i , j - 1] - dp[i][j - 1])

Below is the implementation

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        '''
        let d[i][j] be the optimal difference, then 
        dp[i][j] = max(sum(stones[i + 1: j]) - dp[i + 1][j], sum(stones[i: j - 1]) - dp[i][j - 1])
        '''
        n = len(stones)
        dp = [[0 for j in range(n)] for i in range(n)]
        accs = [0]
        acc = 0
        for stone in stones:
            acc += stone
            accs.append(acc)
        for l in range(2, n + 1):
            for i in range(n + 1 - l):
                j = i + l - 1
                dp[i][j] = max(accs[j + 1] - accs[i + 1] - dp[i + 1][j], accs[j] - accs[i] - dp[i][j - 1])
        return dp[0][n - 1]