877.石子游戏（中等）

参考：
https://labuladong.gitbook.io/algo/mu-lu-ye-2/mu-lu-ye-4/dong-tai-gui-hua-zhi-bo-yi-wen-ti

 /**
     * piles=[3,9,1,2]
     *
     * @param piles
     * @return
     */
    public boolean stoneGame(int[] piles) {
        int n = piles.length;

        if (n <= 0) {
            return false;
        }

        StonePair[][] dp = new StonePair[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = new StonePair();
                dp[i][j].first = 0;
                dp[i][j].second = 0;
            }
        }

        //dp[i][j] 代表的是  piles[i...j] 的中先手和后手的最大值
        //比如  dp[0,1]  就是[3,9]={9,3}  先手拿9  后手只能拿3
        for (int i = 0; i < n; i++) {
            dp[i][i].first = piles[i];
            dp[i][i].second = 0;
        }

        //斜着遍历数组
        for (int left = 2; left <= n; left++) {
            for (int i = 0; i <= n - left; i++) {
                //i 从左边开始     j 从右边开始
                int j = left + i - 1;

                // 这次先手，那么就相当于下次的后手  选piles[i]  还是 选piles[j]
                //dp[i][j].first = Math.max(piles[i] + dp[i + 1][j].second, piles[j] + dp[i][j - 1].second);

                // 下面的这两行 相当于 上面的   Math.max(piles[i] + dp[i + 1][j].second, piles[j] + dp[i][j - 1].second); 的拆分
                int leftPiles = piles[i] + dp[i + 1][j].second;


                int rightPiles = piles[j] + dp[i][j - 1].second;

                //如果 先手选择 piles[i]
                if (leftPiles > rightPiles) {
                    //如果 先手选择 piles[i]
                    dp[i][j].first = leftPiles;
                    dp[i][j].second = dp[i + 1][j].first;
                } else {
                    //如果 先手选择 piles[j]
                    dp[i][j].first = rightPiles;
                    dp[i][j].second = dp[i][j - 1].first;
                }
            }
        }

        //dp[0][n-1]  相当于 就是 选piles[ 0.... n-1]
        StonePair stonePairs = dp[0][n - 1];

        return (stonePairs.first - stonePairs.second) >= 0;
    }

public class StonePair {



    public StonePair() {
    }
    public StonePair(int first, int second) {
        this.first = first;
        this.second = second;
    }

    public int first;
    public int second;
}