2023.05.26 Today's Challenge

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

Stone Game II - LeetCode

근래에 본 DP 문제 중 제일 복잡했던 듯.

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

        def f(p, i, m):
            if i == n:
                return 0
            if dp[p][i][m] != -1:
                return dp[p][i][m]
            res = -1
            if p == 1:
                res = 1000000
            s = 0
            for x in range(1, min(2*m, n-i) + 1):
                s += piles[i+x-1]
                if p == 0:
                    res = max(res, s + f(1, i+x, max(m, x)))
                else:
                    res = min(res, f(0, i+x, max(m, x)))
            dp[p][i][m] = res
            return res
        
        return f(0, 0, 1)