package question;

/*
 @author: Roderland
 @create: 2020年10月30日---16:24
*/
public class Question877 {
 public boolean stoneGame(int[] piles) {
 //return true;
 int[][][] dp = new int[piles.length][piles.length][2];
 for (int k = 0; k < dp.length; k++) {
 for (int i = 0; i < dp.length - k; i++) {
 int j = k + i;
 if (i == j) dp[i][j][0] = piles[i];
 else if (j == i + 1) {
 dp[i][j][0] = Math.max(piles[i], piles[j]);
 dp[i][j][1] = Math.min(piles[i], piles[j]);
 } else {
 if (dp[i][j - 1][1] + piles[j] > dp[i + 1][j][1] + piles[i]) {
 dp[i][j][0] = dp[i][j - 1][1] + piles[j];
 dp[i][j][1] = dp[i][j - 1][0];
 } else {
 dp[i][j][0] = dp[i + 1][j][1] + piles[i];
 dp[i][j][1] = dp[i + 1][j][0];
 }
 }
 }
 }
 return dp[0][piles.length - 1][0] > dp[0][piles.length - 1][1];
 }
}