题目：石子游戏
- 亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子
piles[i]。 - 游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
- 亚历克斯和李轮流进行，亚历克斯先开始。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
- 假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回
true，当李赢得比赛时返回false。
示例：
输入：[5,3,4,5]
输出：true
解释：
亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。
提示：
- 2 <= piles.length <= 500
- piles.length 是偶数。
- 1 <= piles[i] <= 500
- sum(piles)是奇数。
来源：力扣（LeetCode）第877题
分析：
- 这是一道典型的动态规划题。
- 要做出动态规划问题，首先要找到问题的状态和选择。
- 以这道题为例，状态有三种，分别是开始位置索引
i，结束位置索引j，还有在i到j这段位置时，先手的值和后手的值。 - 举个例子，i = 0, j = 0时，表明在第一个索引0时先手明显是piles[0]，而后手没有东西，所以是0。
- 说完状态再来看选择，根据题意，选择就是你可以从开始位置
i拿，也可以从结束位置j拿。 - 然后是状态转移方程，首先每一个i和j所对应的位置都有先后手两种情况，如果我选择拿了i的值，那么剩下留给另一个人的元素就是
i + 1 到 j,而i + 1 到 j是另一个人先手拿的(i+1,j先手就是i,j的后手，因为一人一次)，所以你拿的是i+1, j的后手。 - 同理如果你拿的是右边的
j，那么剩下的就是i, j - 1的后手。 - 因此状态转移方程就是：
max(piles[i] + dp[i+1][j][1], piles[j] + dp[i][j-1][1])。dp是一个三维数组，前两个表示的是i,j位置索引，而1表示的是后手情况，那么0表示的是先手情况。(不一定是0,1也可以是别的，无所谓) - 最后我要的结果就是从0到piles长度的下标，即
dp[0][piles.length-1]。
代码：
class Solution {
public boolean stoneGame(int[] piles) {
int N = piles.length;
int[][][] dp = new int[N][N][2];
for (int i = 0; i < N; i++) {
dp[i][i][0] = piles[i];
dp[i][i][1] = 0;
}
for (int size = 2; size <= N; size++) {
for (int i = 0; i <= N - size; i++) {
int j = i + size - 1; // 由于i,j之间的差一开始会是1，第二次是2...所以这样就保证了j的下标是对的。
int left = piles[i] + dp[i+1][j][1];
int right = piles[j] + dp[i][j-1][1];
if (left < right) { // 每次都取最优情况，不要忘了先手最优，但是后手也要添加进去的。
dp[i][j][0] = right;
dp[i][j][1] = dp[i][j-1][0];
} else {
dp[i][j][0] = left;
dp[i][j][1] = dp[i+1][j][0];
}
}
}
return dp[0][N-1][0] > dp[0][N-1][1]; // 比较先手是否大于后手
}
}
- 你以为这样就结束了？？？
- 如果你写完这段dp代码去测试，你就会发现一件神奇的事情，你无论怎么换测试用例，只要符合题目要求，答案都是true，也就是说只要Alex先手，那么他必赢。
所以第二种方法：
class Solution: def stoneGame(self, piles: List[int]) -> bool: return True
复杂度分析：
- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)
- 虽然是个三维数组，但最后一位是常数2，所以忽略不计。