[leetcode]Stone Game II

유의할점

• 두개의 관점을 하나의 관점으로 생각하는법

• python에서 memoization을 활용하는 방법

  선언만해도 그냥 memo가 된다...

from functools import lru_cache
@lru_cache(None)
def 함수:

• presum을 이용

풀이

함수의 정의 : dp(vector& presum, int p , int m) : 현재 index가 p이고 , 뽑을수있는 최대 개수가 m일때 취할수있는 최대 돌의 개수.

기저사례 : 남아있는 묶음(pile) 개수보다 현재 뽑을수있는 묶음 개수가 크거나 같을때. 무조건 다뽑는것이 이득이므로, 해당 사례를 기저사례로 잡는다.

sum이 계속 사용되므로 presum을 활용하여 미리 sum과정을 생략한다.

A과 B가 번갈아 가면서 뽑는 게임에서 A의 최적값을 생각할때 B를 따로 생각하면 안된다. 즉 다른 파라미터를 사용해서는 안된다는것이다.

두개의 점화식으로 표현가능하다. 해석에 있어서 차이가 존재할뿐 두개는 같은 점화식이다.

res = max(res, s + (presum[p+x] - dp(presum, p+x, max(m,x))));

piles[p] - min(dp(p + x, max(m,x)) for x in range(1, 2 * m +1))

첫번째 점화식에서 s는 내가 현재 취한 돌의 총개수를 뜻하고 presum[p+x]는 s를 취했을때 위치하는 인덱스 p+x 에서 얻을수있는 최대값이다. dp는 p+x 인덱스에서 취할수있는 최대값이다. 해당값은 상대방의 값이기때문에 전채(presum[p+x])에서 해당 값을 빼줌으로써 자신의 최적값을 얻을수있다.

두번째 점화식은 현재 가질수있는 모든 돌 - Alice또는 Bob이 가질수있는 최대돌의 개수중 최소값.

dp는 항상 최적의 값을 도출한다. min값은 해당 최적의 값들 중에서 가장 작은값을 취하는것뿐이다.

고찰

틀린 이유 : dp가 정확히 무엇을 하는지 설명하지 못했다.

정답에서의 dp함수는 현재 인덱스가 p이고 최대 2m개 가질수있는 상태일때 가질수있는 최대 돌의 개수를 반환한다.

내가 생각한 dp함수는 현재 인덱스가 p이고 최대 2m개 가질수있는 상태일때 alice가 만들수있는 최대 돌의 개수이다.

현재 인덱스 , m , player type을 활용해서 player가 A인 경우에는 1개에서 2m개의 값과 다음 dp함수를 더해서 만든 max값을 반환했다.

player가 B인경우 최대 2m개의 값을 skip해서 얻을수있는 최소값이 결국 player A의 값이다. 해당 최소값은 결국 player B의 최대값을 의미하기 때문이다. memo에는 3개의 인자가 들어갔다.

코드

C++ : python에 비교하면 길다.

class Solution {
private:
    int memo[100][100];
    
public:
    int dp(vector<int>& presum, int p , int m){
        if(presum.size() - p <= 2 * m) // presum.size() - p : 남은 숫자의 수 / 2 * m 최대 뽑을수있는 숫자의 수
            return presum[p];
        
        int &res = memo[p][m];
        if(res)
            return res;
        
        for(int x = 1; x <= 2*m; x++){
            int s = presum[p] - presum[p+x];
            res = max(res, s + (presum[p+x] - dp(presum, p+x, max(m,x))));
        }
        
        return res;
    }
    
    int stoneGameII(vector<int>& piles) {
        vector<int> presum = piles;
        for(int i = piles.size()-2; i >= 0; i--)
            presum[i] += presum[i+1];
        memset(memo,0,sizeof(memo));
        
        return dp(presum,0,1);
    }
};

//presum을 이용한다.
//memo를 제대로 이용한다.

Python3 : 좋다..

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        N = len(piles)
        for i in range(N - 2, -1, -1):
            piles[i] += piles[i + 1] # piles는 현재 presum으로 변경되었다.
        from functools import lru_cache # memoization에 사용.
        @lru_cache(None) # 크기 제한이 없음.
        def dp(p, m):
            if p + 2 * m >= N: return piles[p] # p는 현재 인덱스이고. 2*m 만큼 더할수있다.
            return piles[p] - min(dp(p + x, max(m,x)) for x in range(1, 2 * m +1))
        return dp(0,1)