_1140. Stone Game II.md

1140. Stone Game II

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 20, 2024

Last updated : August 20, 2024

---

Related Topics : Array, Math, Dynamic Programming, Prefix Sum, Game Theory

Acceptance Rate : 73.07 %

---

The question description is kinda bad... Esp compared to the other Stone Game questions.

---

Solutions

• m1140.py

Python

m1140.py

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        dp = [[0] * len(piles) for _ in range(len(piles))]

        sfx = piles.copy()
        for i in range(2, len(piles) + 1) :
            sfx[-i] += sfx[-i + 1]

        def recurs(sfx: List[int], maxx: int, indx: int, dp: List[List[int]]) -> int :
            if indx + 2 * maxx >= len(sfx) :
                return sfx[indx]
            if dp[indx][maxx] :
                return dp[indx][maxx]

            out = inf
            for i in range(1, 2 * maxx + 1) :
                out = min(out, recurs(sfx, max(i, maxx), indx + i, dp))

            dp[indx][maxx] = sfx[indx] - out
            return dp[indx][maxx]

        return recurs(sfx, 1, 0, dp)