leetcode 1140 - Stone Game II

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

풀이

처음에 M = 1 인 상태에서, 1 <= x <= 2X 개의 pile을 가져가고, 그 이후로도 max(M, X) 개를 가져갈 수 있다.

한눈에 봐서 최적의 선택을 모르겠으니 전부 해보면 된다. 이때 중복된 연산을 하지 않기 위해 효율적으로 아래와 같이 d값을 정의한다.

d[i][j] = pile의 i번째부터 시작하고, M = j인 상태에서 선공하는 사람이 가져가는 돌의 합

 

재귀적으로 마지막까지 가서 하나의 pile이 남은 경우 d[n-1][*] = piles[n-1] 이 된다.

모든 경우를 구해봐야 $O(n^2)$ 짜리의 d 배열을 채우는 정도이고, 각 상태를 채우기 위해 최대 n가지 행동을 다 해보므로 전체 시간 복잡도는 $O(n^3)$이 된다.

 

 

코드

class Solution {
public:
    vector<vector<int>> d;
    vector<int> sum;
    int n;
    int stoneGameII(vector<int>& piles) {
        n = piles.size();
        d.resize(n, vector<int>(n+1, -1));
        sum.resize(n+1);
        for(int i = n-1; i >= 0; i--) {
            sum[i] = sum[i+1] + piles[i];
        }
        
        return dfs(0, 1);
    }
    
    int dfs(int index, int m) {
        if(index >= n) return 0;
        if(d[index][m] != -1) return d[index][m];

        int ans = 0;
        for(int i = index; i < min(n, index + 2*m); i++) {
            ans = max(ans, sum[index] - dfs(i+1, max(m, i-index+1)));
        }

        return d[index][m] = ans;
    }
};