题目描述
这是 LeetCode 上的 877. 石子游戏 ，难度为 中等。
Tag : 「区间 DP」、「博弈论」
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 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) 是奇数。
动态规划
定义 f[l][r]f[l][r] 为考虑区间 [l,r][l,r]，在双方都做最好选择的情况下，先手与后手的最大得分差值为多少。
那么 f[1][n]f[1][n] 为考虑所有石子，先手与后手的得分差值：
- f[1][n] > 0f[1][n]>0，则先手必胜，返回
True - f[1][n] < 0f[1][n]<0，则先手必败，返回
False
不失一般性的考虑 f[l][r]f[l][r] 如何转移。根据题意，只能从两端取石子（令 pilespiles 下标从 11 开始），共两种情况：
- 从左端取石子，价值为 piles[l - 1]piles[l−1]；取完石子后，原来的后手变为先手，从 [l + 1, r][l+1,r] 区间做最优决策，所得价值为 f[l + 1][r]f[l+1][r]。因此本次先手从左端点取石子的话，双方差值为：
piles[l - 1] - f[l + 1][r]piles[l−1]−f[l+1][r]
- 从右端取石子，价值为 piles[r - 1]piles[r−1]；取完石子后，原来的后手变为先手，从 [l, r - 1][l,r−1] 区间做最优决策，所得价值为 f[l][r - 1]f[l][r−1]。因此本次先手从右端点取石子的话，双方差值为：
piles[r - 1] - f[l][r - 1]piles[r−1]−f[l][r−1]
双方都想赢，都会做最优决策（即使自己与对方分差最大）。因此 f[l][r]f[l][r] 为上述两种情况中的最大值。
根据状态转移方程，我们发现大区间的状态值依赖于小区间的状态值，典型的区间 DP 问题。
按照从小到大「枚举区间长度」和「区间左端点」的常规做法进行求解即可。
代码：
class Solution { public boolean stoneGame(int[] ps) { int n = ps.length; int[][] f = new int[n + 2][n + 2]; for (int len = 1; len <= n; len++) { // 枚举区间长度 for (int l = 1; l + len - 1 <= n; l++) { // 枚举左端点 int r = l + len - 1; // 计算右端点 int a = ps[l - 1] - f[l + 1][r]; int b = ps[r - 1] - f[l][r - 1]; f[l][r] = Math.max(a, b); } } return f[1][n] > 0; } } 复制代码
- 时间复杂度：O(n^2)O(n2)
- 空间复杂度：O(n^2)O(n2)
博弈论
事实上，这还是一道很经典的博弈论问题，也是最简单的一类博弈论问题。
为了方便，我们称「石子序列」为石子在原排序中的编号，下标从 11 开始。
由于石子的堆数为偶数，且只能从两端取石子。因此先手后手所能选择的石子序列，完全取决于先手每一次决定。
由于石子的堆数为偶数，对于先手而言：每一次的决策局面，都能「自由地」选择奇数还是偶数的序列，从而限制后手下一次「只能」奇数还是偶数石子。
具体的，对于本题，由于石子堆数为偶数，因此先手的最开始局面必然是 [奇数, 偶数][奇数,偶数]，即必然是「奇偶性不同的局面」；当先手决策完之后，交到给后手的要么是 [奇数,奇数][奇数,奇数] 或者 [偶数,偶数][偶数,偶数]，即必然是「奇偶性相同的局面」；后手决策完后，又恢复「奇偶性不同的局面」交回到先手 ...
不难归纳推理，这个边界是可以应用到每一个回合。
因此先手只需要在进行第一次操作前计算原序列中「奇数总和」和「偶数总和」哪个大，然后每一次决策都「限制」对方只能选择「最优奇偶性序列」的对立面即可。
同时又由于所有石子总和为奇数，堆数为偶数，即没有平局，所以先手必胜。
代码：
class Solution { public boolean stoneGame(int[] piles) { return true; } } 复制代码
- 时间复杂度：O(1)O(1)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.877 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个
系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
