1140. Stone Game II

Link

Solution

DFS + memo

 public int stoneGameII(int[] piles) {
        int N = piles.length;
        int[][] memo = new int[N][N];
        int[] preSum = new int[N];
        preSum[N-1] = piles[N-1];
        for(int i = N-2; i >= 0; i--){
            preSum[i] = preSum[i+1] + piles[i];
        }
        return dfs(preSum, memo, 0, 1);
    }
    
    public int dfs(int[] preSum, int[][] memo, int index, int m){
        if(index + 2*m >= preSum.length){
            return preSum[index];
        }
        if(memo[index][m] != 0) return memo[index][m];
        int ret = 0;
        for(int i = 1; i <= 2*m; i++){
            int take = preSum[index] - preSum[index+i];
            ret = Math.max(ret, take + preSum[index+i] - dfs(preSum, memo, index+i, Math.max(m, i)));
        }
        memo[index][m] = ret;
        return ret;
        
    }