877. Stone Game

本题最难的是识别题目的意图，
Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.
理解play optimally了，就能顺利解题，
我的解法是用dynamic programming:

Helper[][] dp = new Helper[piles.length][piles.length];

dp[i][j].first是先选的人能获得的最大值，dp[i][j].second代表后选的人，在先选的人一直做出最优解的前提下，获得的最大值：

dp[i][j].first = dp[i][j-1].second + piles[j];
dp[i][j].second = dp[i][j-1].first;
if (dp[i+1][j].second + piles[i] > dp[i][j].first) {
    dp[i][j].first = dp[i+1][j].second + piles[i];
    dp[i][j].second = dp[i+1][j].first;
}

理解了这段代码，本题就算是顺利解出了。
代码如下：

public class Solution {
    public boolean stoneGame(int[] piles) {
        Helper[][] dp = new Helper[piles.length][piles.length];
        for (int i = 0; i < piles.length - 1; ++i) {
            dp[i][i+1] = new Helper();
            dp[i][i+1].first = Math.max(piles[i], piles[i+1]);
            dp[i][i+1].second = Math.min(piles[i], piles[i+1]);
        }
        for (int len = 3; len <= piles.length; ++len) {
            for (int i = 0; i + len <= piles.length; ++i) {
                int j = i + len - 1;
                dp[i][j] = new Helper();
                // case 1:
                dp[i][j].first = dp[i][j-1].second + piles[j];
                dp[i][j].second = dp[i][j-1].first;
                if (dp[i+1][j].second + piles[i] > dp[i][j].first) {
                    dp[i][j].first = dp[i+1][j].second + piles[i];
                    dp[i][j].second = dp[i+1][j].first;
                }
            }
        }
        return dp[0][piles.length-1].first > dp[0][piles.length-1].second;
    }
}
class Helper {
    public int first;
    public int second;
    public Helper() {
        first = 0;
        second = 0;
    }
}

彩蛋：
本题还有一个很逆天的解法，如果够聪明的话，就能想到先选的人不可能输：

• 所有奇数位的和，所有偶数位的和必然有一个比另一个大
  
• 假设奇数位的和大，先选的人可以一直选择奇数位，逼迫后者一直选偶数位，反之同理
  
• 所以本题可以直接返回true