[leetcode]1140. Stone Game II

1140. Stone Game II

 

Alex and Lee 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. 

Alex and Lee take turns, with Alex starting first.  Initially, M = 1.

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).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

class Solution(object):
    def stoneGameII(self, piles):
        n = len(piles)
        for i in range(n-2,-1,-1):
            piles[i] += piles[i+1]
        cache ={}
        def dfs(i, m):
            if (i,m) in cache:
                return cache[(i,m)]
            
            if i+2*m >=n:
                cache[(i,m)] = piles[i]
                return cache[(i,m)]
            
            max_piles = piles[i] - min([dfs(i+x,max(x,m)) for x in range(1,2*m+1)])
            cache[(i,m)] = max_piles
            return cache[(i,m)]
        return dfs(0,1)

minmax알고리즘 쓰는 문제 처음풀어본다...

너무신기하다

너무어려다

여기에다가 dp 메모이제이션을 추가한 코드이다. 

와우 와우와우