经典区间 DP & 经典博弈游戏

题目描述

这是 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 原题链接和其他优选题解。