LC 877. 石子游戏

题目描述

这是 LeetCode 上的 877. 石子游戏 ，难度为 中等。

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 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]$ 为考虑区间 $[l,r]$，在双方都做最好选择的情况下，先手与后手的最大得分差值为多少。

那么 $f[1][n]$ 为考虑所有石子，先手与后手的得分差值：

• $f[1][n] > 0$，则先手必胜，返回 True
• $f[1][n] < 0$，则先手必败，返回 False

不失一般性的考虑 $f[l][r]$ 如何转移。根据题意，只能从两端取石子（令 $piles$ 下标从 $1$ 开始），共两种情况：

• 从左端取石子，价值为 $piles[l - 1]$；取完石子后，原来的后手变为先手，从 $[l + 1, r]$ 区间做最优决策，所得价值为 $f[l + 1][r]$。因此本次先手从左端点取石子的话，双方差值为：

$$piles[l - 1] - f[l + 1][r]$$

• 从右端取石子，价值为 $piles[r - 1]$；取完石子后，原来的后手变为先手，从 $[l, r - 1]$ 区间做最优决策，所得价值为 $f[l][r - 1]$。因此本次先手从右端点取石子的话，双方差值为：

$$piles[r - 1] - f[l][r - 1]$$

双方都想赢，都会做最优决策（即使自己与对方分差最大）。因此 $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(n^2)$

---

博弈论

事实上，这还是一道很经典的博弈论问题，也是最简单的一类博弈论问题。

为了方便，我们称「石子序列」为石子在原排序中的编号，下标从 $1$ 开始。

由于石子的堆数为偶数，且只能从两端取石子。因此先手后手所能选择的石子序列，完全取决于先手每一次决定。

由于石子的堆数为偶数，对于先手而言：每一次的决策局面，都能「自由地」选择奇数还是偶数的序列，从而限制后手下一次「只能」奇数还是偶数石子。

具体的，对于本题，由于石子堆数为偶数，因此先手的最开始局面必然是 $[奇数, 偶数]$，即必然是「奇偶性不同的局面」；当先手决策完之后，交到给后手的要么是 $[奇数,奇数]$ 或者 $[偶数,偶数]$，即必然是「奇偶性相同的局面」；后手决策完后，又恢复「奇偶性不同的局面」交回到先手 …

不难归纳推理，这个边界是可以应用到每一个回合。

因此先手只需要在进行第一次操作前计算原序列中「奇数总和」和「偶数总和」哪个大，然后每一次决策都「限制」对方只能选择「最优奇偶性序列」的对立面即可。

同时又由于所有石子总和为奇数，堆数为偶数，即没有平局，所以先手必胜。

代码：

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

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.877 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。