Stone Game II #

Link: Stone Game II

Problem #

Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alice and Bob take turns, with Alice starting first.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X). Initially, M = 1.

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

Thoughts #

The problem wants us to maximize the number of stones Alice can get.

Since 2 player plays optimally, we only care about how much current player can get most, which also means the other player can get least even if he plays optimally.

Solution #

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        
        suffix_sum = [0] * n
        suffix_sum[-1] = piles[-1]
        for i in range(n - 2, -1, -1):
            suffix_sum[i] = suffix_sum[i + 1] + piles[i]
        
        # use suffix sum to easily calculate 
        # how many stones remain at each condition

        @cache
        def dp(i, m):
            if i + 2 * m >= n:
                return suffix_sum[i] # Take all remaining stones
            max_stones = 0
            for x in range(1, 2 * m + 1):
                max_stones = max(max_stones, suffix_sum[i] 
                                  - dp(i + x, max(m, x)))
            return max_stones
        return dp(0, 1)

Explanation #

1. We use suffix sum to speed up calculation
2. The dp`` function returns the maximum number of stones the current player can get starting from index iwithM = m`.
3. Our base case is when we can take all remaining stones, which means we can return the suffix sum at that point
4. We want to go over all the cases we can get at this condition i and m and find out the minium number of stones the other player can get. By subtracting, we got the number of stones the current player can get at this condition. We want to maximize this number, so we update our answer by comparing with the current answer.
5. Start from index 0 and M = 1, we can get the answer.

Insights #

• In game theory, usually we don’t care about who is playing, focus on the best strategy is more important.