877. Stone Game

Problem

Stone Game

Approach

1. We can’t define dp[i] be the largest score Alex can get after i-th turns. Because j-th turn which is behind i-th can influence the expected result.
2. Approach 1: Let dp[i, j] be the expected result. It means the largest score Alex gets from these piles of index from i to j. And, dp[i, j] can be formulated from dp[i + 1, j] and dp[i, j - 1]. More precisely, dp[i, j] = Max(dp[i, j - 1] + piles[j], dp[i + 1, j] + piles[i])
3. Approach 2: it’s same as the previous one. But the way to update dp[i][j] is different. dp[i][j] = true if dp[i + 2][j] == true || dp[i][j - 2] || dp[i + 1][j - 1]. Because every time, Alex and Lee will choose two piles of stones. So, the dp array is updated by its’ subarray whose length is smaller by two.

Code

// approach 1
class Solution {
    public int helper(int[][] dp, int i, int j, int[] piles){
        if(j - i + 1 == piles.length / 2) return 0;
        if(dp[i][j] < Integer.MAX_VALUE){
            return dp[i][j];
        }
        dp[i][j] = Math.max(helper(dp, i, j - 1, piles) + piles[j],
                           helper(dp, i + 1, j, piles) + piles[i]);
        return dp[i][j];
    }
    public boolean stoneGame(int[] piles) {
        int N = piles.length;
        int[][] dp = new int[N][N];
        for(int i = 0; i < N; i ++){
            for(int j = 0; j < N; j ++){
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        int ans = helper(dp, 0, N - 1, piles);
        int total = 0;
        for(int i = 0; i < N; i ++){
            total += piles[i];
        }
        return ans > total - ans;
    }
}

// approach 2
class Solution {
    public boolean stoneGame(int[] piles) {
        int N = piles.length;
        boolean[][] dp = new boolean[N][N];
        for(int i = 0; i < N; i += 2){
            dp[i][i + 1] = true;
        }
        for(int len = 4; len <= N; len += 2){
            for(int i = 0; i < N; i ++){
                int j = i + len - 1;
                if(j >= N){
                    break;
                }
                if(!dp[i][j] && j >= 1 && i < N - 1){
                    dp[i][j] = dp[i + 1][j - 1];
                }
                if(!dp[i][j] && j >= 2){
                    dp[i][j] = dp[i][j - 2];
                }
                if(!dp[i][j] && i + 2 < N){
                    dp[i][j] = dp[i + 2][j];
                }
            }
        }
        return dp[0][N - 1];
    }
}