Stone Game II

Leetcode Problem:

• Stone Game II

Summary

• The problem is to find the maximum number of stones Alice can get in a game where Alice and Bob take turns taking stones from piles.

Approach

• The approach is to use dynamic programming and memoization to calculate the maximum number of stones Alice can get
• The idea is to calculate the suffix sums of the piles and then use a recursive function to calculate the maximum number of stones Alice can get by taking stones from the first X piles, where 1 <= X <= 2M.

Complexity

• O(n * 2M) where n is the number of piles and M is the maximum number of piles Alice can take in a turn.

Explain

• The solution code first calculates the suffix sums of the piles
• Then it defines a recursive function take_stones that calculates the maximum number of stones Alice can get by taking stones from the first X piles
• The function uses memoization to avoid redundant calculations
• Finally, the solution returns the result of the recursive function with m = 1.

Solution Code:

from functools import lru_cache


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        suffix_sums = [0 for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            suffix_sums[i] = piles[i] + suffix_sums[i + 1]

        @lru_cache(maxsize=None)
        def take_stones(i, m):
            if i >= n:
                return 0
            if i + 2 * m >= n:
                return suffix_sums[i]
            return suffix_sums[i] - min(
                take_stones(i + x, max(m, x)) for x in range(1, 2 * m + 1)
            )

        return take_stones(0, 1)