Leetcode 1240 Solution

This article provides solution to leetcode question 1240 (stone-game-ii)
Categories:
Tags:
Access this page by simply typing in "lcs 1240" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/stone-game-ii

Solution

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        cache = {}

        def play(piles, s, i, M):
            if i == len(piles):
                return 0

            key = (i, M)
            if key in cache:
                return cache[key]

            start_pile = i
            end_pile = i

            options = []

            pile_sum = 0
            while end_pile < len(piles) and end_pile - start_pile + 1 <= 2 * M:
                pile_sum += piles[end_pile]
                s -= piles[end_pile]

                opponent_opt = play(piles, s, end_pile + 1, max(end_pile - start_pile + 1, M))

                options.append(pile_sum + s - opponent_opt)

                end_pile += 1

            cache[key] = max(options)
            return cache[key]

        return play(piles, sum(piles), 0, 1)