简介
石子游戏其实就是多人博弈，如何求最优结果。它存在很多变种，比如不同的取石方式，不同的计算输赢的方式，在这里做一个汇总。
1.只能从两端取，取的数量为得分
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。
leetcode
动态规划
解题思路：
- 首先是状态表示，利用一个二维数组，二维数组的两个下标分别代表原始数组的左右端下标，数组当前值表示这两个下标之下，先手比后手多的得分；
- 然后是状态转移，分别取左端和右端情况下的最大值。取某一端时，得分差应当是那个石头的值减去剩余部分先手的最大差。
- 区间DP的枚举方式都是先从小到大枚举区间，再枚举起始点。
class Solution {
public boolean stoneGame(int[] piles) {
int n = piles.length;
int[][] f = new int[n][n];
// 初始化区间长度为1时的值
for(int i = 0; i < n; i++) {
f[i][i] = piles[i];
}
// 先枚举区间长度
for(int len = 2; len <= n; len ++) {
// 再枚举起点
for(int i = 0; i + len - 1 < n; i++) {
// 计算终点
int j = i + len - 1;
// 状态转移，再取左右两个端点中求最大值
f[i][j] = Math.max(piles[i] - f[i + 1][j], piles[j] - f[i][j - 1]);
}
}
return f[0][n - 1] > 0;
}
}
深搜
解题思路：
- 从两段开始向下搜索，每次需要搜索分别取左右两端的两种情况；
- 需要进行记忆化，利用一个数组记录每种搜索情况，剪枝。
class Solution {
Integer[][] m;
public boolean stoneGame(int[] piles) {
int n = piles.length;
m = new Integer[n][n];
return dfs(piles, 0, n - 1) > 0;
}
public int dfs(int[] p, int i, int j) {
if(i > j) return 0;
if(m[i][j] != null) return m[i][j];
int ans = Math.max(p[i] - dfs(p, i + 1, j), p[j] - dfs(p, i, j - 1));
m[i][j] = ans;
return ans;
}
}
2.每次可以取前面一段，取的数量为得分
亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。
在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
游戏一直持续到所有石子都被拿走。
假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。
leetcode
解题思路：采用动态规划的方法。
- 首先是状态标识，不同于上面的题，这道题的取石头的堆数会发生改变，而取得方向不会改变，所以，状态标识中，需要有取石头得起始位置，和当前的M值。通过一个数组，一维表示取得起始位置，二维表示当前得m值。f[i][j]表示从第i位取，M等于j时，先手的最大得分，这样f[0][1]就是最开始得
- 然后是状态转移，需要从间距短的枚举到区间大的，区间DP常规操作。枚举了起始点位置之后，再枚举m，其中m的最大值不能超过数组总长度。然后分两种情况：
- 可以拿完后面的所有石头，那么当前得分应当时后面石头数之和。
- 不能拿完，当前的值应当是区间数组的和减去后手的最大值，具体还是看代码吧。
class Solution {
public int stoneGameII(int[] piles) {
int n = piles.length, sum = 0;
// 状态表示数组，表示数组从i开始，M等于j的先手最大得分
int[][] f = new int[n][n + 1];
// 先枚举其实位置，间距从小到达
for(int i = n - 1; i >= 0; i--) {
// 后缀和
sum += piles[i];
// 再枚举m
for(int m = 1; m <= n; m ++) {
if(i + 2 * m >= n) {
// 如果可以拿完，那么就直接获得后面得总和
f[i][m] = sum;
} else {
// 不能拿完，就需要枚举所有得情况
for(int x = 1; x <= 2 * m; x++) {
// 这里这个状态转移很重要
// 如果不能拿完，那么当前得分应当是总和减去后手的最优得分
f[i][m] = Math.max(f[i][m], sum - f[i + x][Math.max(x, m)]);
}
}
}
}
// 从0开始，m等于1就是题目要求的先手最优得分
return f[0][1];
}
}
3.每次可以从前面取1、2或者3份
Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组 stoneValue 给出。
Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。
每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。
假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，平局（分数相同）返回 "Tie" 。
leetcode
动态规划
解题思路：
- 首先是状态表示，这题和上面那题很类似，不过上面的可取份数是不确定得，而这题是1、2或者3，所以，可以在上面那题的基础上，去掉一个维度，用以为数组就可以表示，以某个位置为起点，先手的最大得分；
- 然后是状态转移，先从小到大开始枚举区间，然后再枚举取1、2或者3的情况下的最大值。当前的得分应当是后面的所有分数减去获取了前面一段位置之后，相应位置的后手得分。
- 不同的是，这道题中会存在负分，所以，再每个起点的时候，需要将当前分数初始化为最小数值。
class Solution {
public String stoneGameIII(int[] s) {
int n = s.length;
int[] f = new int[n + 1];
int sum = 0;
// 区间从小到大开始枚举起点位置
for(int i = n - 1; i >= 0; i--) {
// 求后缀和
sum += s[i];
// 初始化当前分数
f[i] = Integer.MIN_VALUE;
// 枚举三种情况
for(int j =i; j <= i + 2 && j < n; j++) {
// 状态转移
f[i] = Math.max(f[i], sum - f[j + 1]);
}
}
if(f[0] > sum - f[0]) return "Alice";
else if(f[0] < sum - f[0]) return "Bob";
else return "Tie";
}
}
深搜
解题思路：
- 搜索每种情况的最大值
class Solution {
Integer[] m;
public String stoneGameIII(int[] s) {
int n = s.length;
m = new Integer[n];
int r = dfs(s, 0);
if(r > 0) return "Alice";
else if(r < 0) return "Bob";
else return "Tie";
}
public int dfs(int[] s, int cur) {
if(cur >= s.length) return 0;
if(m[cur] != null) return m[cur];
// 搜索每种情况
int ans = s[cur] - dfs(s, cur + 1);
if(cur + 1 < s.length) ans = Math.max(ans, s[cur] + s[cur + 1] - dfs(s, cur + 2));
if(cur + 2 < s.length) ans = Math.max(ans, s[cur] + s[cur + 1] + s[cur + 2] - dfs(s, cur + 3));
m[cur] = ans;
return ans;
}
}
4.只能取平方数，取完最后的就获胜
Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。
一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石子堆里没有石子了，则无法操作的玩家输掉游戏。
给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。
leetcode
解题思路：动态规划
- 首先还是状态表示，利用一个数组表示当前石头数量下，先手是否能够获胜;
- 然后还是状态转移，枚举平方数，看看能不能枚举到对方输的情况，对方输了，那我们先手不就赢了。
class Solution {
public boolean winnerSquareGame(int n) {
boolean[] f = new boolean[n + 1];
List<Integer> mode = new ArrayList<>();
// 先枚举平方数，在平方数的状态下，肯定赢
for(int i = 1; i * i <= n; i++) {
mode.add(i * i);
f[i * i] = true;
}
// 从区间小的情况下开始枚举
for(int i = 2; i <= n; i++) {
// 再枚举平方数，如果当前状态能赢，或者越界了，就不继续枚举了
for(int j = 0; j < mode.size() && i > mode.get(j) && !f[i]; j++) {
// 当前的输赢就是取了这堆石头之后，下一手的输赢取反
f[i] = !f[i - mode.get(j)];
}
}
return f[n];
}
}
5.只能从两端取，剩余和为得分
石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。
鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。
leetcode
解题思路：
- 深度优先搜索不进行记忆的话会超时，只能采用dp的思想来做；
- 首先是状态表示，用一个二维数组，表示指定区间内，先手的最大差值；
- 状态转移，当前状态就是分两种情况，拿掉左端或者右端，获得当前得分，再减去以后手的先手差值，再在左右端中取最大值；
- 这就是一个区间dp的模板题，先枚举区间长度，再枚举起点。
class Solution {
public int stoneGameVII(int[] w) {
int n = w.length;
int[] s = new int[n + 1];
// 为了在O1的时间内获取两点之间的和，这里先去前缀和
for(int i = 1; i <= n; i++) s[i] = s[i - 1] + w[i - 1];
// 状态表示数组
int[][] f = new int[n + 1][n + 1];
// 先枚举区间长度
for(int len = 2; len <= n; len++) {
// 再枚举起点
for(int i = 1; i + len - 1 <= n; i++) {
// 终点
int j = i + len - 1;
// 状态转移，取左端点或者又端点的最大值
f[i][j] = Math.max(s[j] - s[i] - f[i + 1][j], s[j - 1] - s[i - 1] - f[i][j -1]);
}
}
return f[1][n];
}
}