简介
石子游戏其实就是多人博弈，如何求最优结果。它存在很多变种，比如不同的取石方式，不同的计算输赢的方式，在这里做一个汇总。
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
// 先枚举平方数，在平方数的状态下，肯定赢
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];
}
}
6.随便拿1-3块，拿到最后的人就赢
你和你的朋友，两个人一起玩 Nim 游戏： 桌子上有一堆石头。 你们轮流进行自己的回合，你作为先手。 每一回合，轮到的人拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。 leetcode
class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
7.每次拿一半，总和少的部分为得分
几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。 游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。 只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。 返回 Alice 能够获得的最大分数 。 leetcode
解题思路：
这类取石头的游戏大多是可以用一维的区间DP，来完成，因为当前区间的状态，可以从拿走时候后剩下区间的状态获取过来。首先是状态表示，利用一个二维数组，表示所有可能的区间下，A的最大得分；然后是状态转移，当前区间的最大值，一定是从拿走石子后剩下的区间状态得分加上这段区间石子的总和转移过来的；最后返回整个区间的得分；在枚举区间的过程中，往往都是先从小到大枚举区间长度，再枚举起点，这样，长的可以从短的状态转移过来。
class Solution {
public int stoneGameV(int[] stoneValue) {
int n = stoneValue.length;
// 建立状态表示数组
int[][] f = new int[n][n];
// 前缀和，快速获取范围内的元素和
int[] sub = new int[n + 1];
// 获取前缀和
for(int i = 0; i < n; i++) {
sub[i + 1] = sub[i] + stoneValue[i];
}
int res = 0;
// 枚举所有情况，先枚举区间长度，再枚举起点和终点
for(int len = 2; len <= n; len ++) {
for(int i = 0; i + len - 1 < n; i ++) {
int j = i + len - 1;
// 枚举所有的切分点
for(int k = i; k < j; k ++) {
// 分别计算左边和右边的和
int left = sub[k + 1] - sub[i];
int right = sub[j + 1] - sub[k + 1];
// 计算每种情况下的状态转移，当前状态就是从切分后剩下的区间状态转移过来的
if(left > right) {
f[i][j] = Math.max(f[i][j], right + f[k + 1][j]);
} else if(left < right) {
f[i][j] = Math.max(f[i][j], left + f[i][k]);
} else {
f[i][j] = Math.max(f[i][j], Math.max(left + f[i][k], right + f[k + 1][j]));
}
}
}
}
return f[0][n - 1];
}
}