一、题目

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

点击查看原题
难度级别：中等

二、思路

1）动态规划

根据暴力法的思想，可以将玩家的选择看作一个二叉树（只可以选择最前面和最后面），根据选择的过程，可以直接找到重复子问题：当选择剩下(i, j)这个区间的石子没拿时，两个玩家在这个区间发挥最佳水平拿到的石子数量应该是恒定的（因为谁先手确定了）。
设置二维数组dp[i][j]表示在(i, j)区间两个玩家发挥最佳水平能够拿到的石子数量的差值（也就是两个玩家都是最佳策略，如果记录玩家手中石子数量，还需要区分谁拿的第几轮，比较麻烦），可以得到状态转移：

这里为什么是piles[i]-dp[i+1][j]呢？单独选一个分支来看

这就是认为第i次为先手的情况下，先手玩家石子数量和-后手玩家的石子数量和，每次都站在每个玩家的角度，使其最大化
最后dp[0][piles.length - 1]为亚历克斯先手拿所有石头，能够比另一个多多少石头的数量，如果大于零则赢

2）数学方法

由于题目给定数据不可能平手，将每个人的选择看作二叉树的话，最开始的先手可以选择走任意的二叉树，那就必然赢

三、代码

1）动态规划

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

时间复杂度为O(n````)，空间复杂度为O(n````)
对其空间进行优化，因为i的状态只依赖于i+1时状态，可以将空间优化为一维

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

时间复杂度为O(n````)，空间复杂度为O(n)

2）数学方法

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}

时间复杂度为O(1)，空间复杂度为O(1)