877. Stone Game

Link

Solution

dp[i][j] means the current picker can win how many stores when current existing piles are [i, i+1.., j]

//pick piles[i] vs pick piles[j]

dp[i][j] = Math.max( piles[i] - dp[i+1, j], piles[j] - dp[i][j-1];)

 public boolean stoneGame(int[] piles) {
        int[][] dp = new int[piles.length][piles.length];
        
        for(int i = 0; i < piles.length; i++){
            dp[i][i] = piles[i];
        }
        
        for(int i = 0; i < piles.length-1; i++){
            for(int j = i+1; j < piles.length; j++){
                dp[i][j] = Math.max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
            }
        }
        return dp[0][piles.length-1] > 0;
    }