题目出处
https://leetcode-cn.com/problems/stone-game/
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。
亚历克斯和李轮流进行,亚历克斯先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。
假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true ,当李赢得比赛时返回 false 。
思路:常见的为动态规划算法,轮流去很容易想到递归,然后用动态规划优化,定义二维数组 dp,其行数和列数都等于石子的堆数,元素表示当石子堆的元素剩从i到j时,状态转移方程如下
dp[i][j]=max(piles[i]−dp[i+1][j],piles[j]−dp[i][j−1])
class Solution { public boolean stoneGame(int[] piles) { int length = piles.length; int[][] dp = new int[length][length]; for (int i = 0; i < length; i++) { dp[i][i] = piles[i]; } for (int i = length - 2; i >= 0; i--) { for (int j = i + 1; j < length; j++) { dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]); } } return dp[0][length - 1] > 0; }}
另一种方法为数学思路
假设有 nnn 堆石子,nnn 是偶数,则每堆石子的下标从 000 到 n−1n-1n−1。根据下标将 nnn 堆石子分成两组,每组有 n2\frac{n}{2}2n 堆石子,下标为偶数的石子堆属于第一组,下标为奇数的石子堆属于第二组。
在此种状态下,作为先手的人可以选择自己拿奇数组还是偶数组(拿第一个还是最后一个),后手只能根据先手的选择来进行选择,无论后手怎么选择,他拿到的都是奇数组或者偶数组,即先手可以选择自己拿奇数组或者偶数组中较大的一组,则先手必赢
class Solution { public boolean stoneGame(int[] piles) { return true; }}
2,黑板异或游戏
https://leetcode-cn.com/problems/chalkboard-xor-game/
黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字,Alice 先手。如果擦除一个数字后,剩余的所有数字按位异或运算得出的结果等于 0 的话,当前玩家游戏失败。 (另外,如果只剩一个数字,按位异或运算得到它本身;如果无数字剩余,按位异或运算结果为 0。)
并且,轮到某个玩家时,如果当前黑板上所有数字按位异或运算结果等于 0,这个玩家获胜。
假设两个玩家每步都使用最优解,当且仅当 Alice 获胜时返回 true。
思路
对于本题,给定的是判断「胜利」的规则(在给定序列的情况下,如果所有数值异或和为 000 可立即判断胜利,其他情况无法立即判断胜负),那么我们应该优先判断何为「先手必胜态」,如果不好分析,才考虑分析后手的「必败态」。
接下来是分情况讨论:
如果给定的序列异或和为 000,游戏开始时,先手直接获胜:
由此推导出性质一:给定序列 nums 的异或和为 000,先手处于「必胜态」,返回 True。
2. 如果给定序列异或和不为 000,我们需要分析,先手获胜的话,序列会满足何种性质:
显然如果要先手获胜,则需要满足「先手去掉一个数,剩余数值异或和必然不为 0;同时后手去掉一个数后,剩余数值异或和必然为 000」。
换句话说,我们需要分析什么情况下「经过一次后手操作」后,序列会以上述情况 1 的状态,回到先手的局面。
也就是反过来分析想要出现「后手必败态」,序列会有何种性质。
假设后手操作前的异或和为 Sum(Sum/0),「后手必败态」意味着去掉任意数字后异或和为 000。
同时根据「相同数值异或结果为 000」的特性,我们知道去掉某个数值,等价于在原有异或和的基础上异或上这个值。
则有:Sum′=Sum⊕nums[i]=0
由于是「后手必败态」,因此 iii 取任意一位,都满足上述式子。
则有:
Sum⊕nums[0]=…=Sum⊕nums[k]=…=Sum⊕nums[n−1]=0Sum ⊕ nums[0] = … = Sum ⊕ nums[k] = … = Sum ⊕ nums[n - 1] = 0 Sum⊕nums[0]=…=Sum⊕nums[k]=…=Sum⊕nums[n−1]=0
同时根据「任意数值与 0 异或数值不变」的特性,我们将每一项进行异或:
(Sum⊕nums[0])⊕…⊕(Sum⊕nums[k])⊕…⊕(Sum⊕nums[n−1])=0(Sum ⊕ nums[0]) ⊕ … ⊕ (Sum ⊕ nums[k]) ⊕ … ⊕ (Sum ⊕ nums[n - 1]) = 0 (Sum⊕nums[0])⊕…⊕(Sum⊕nums[k])⊕…⊕(Sum⊕nums[n−1])=0
根据交换律进行变换:
(Sum⊕Sum⊕…⊕Sum)⊕(nums[0]⊕…⊕nums[k]⊕…⊕nums[n−1])=0(Sum ⊕ Sum ⊕ … ⊕ Sum) ⊕ (nums[0] ⊕ … ⊕ nums[k] ⊕ … ⊕ nums[n - 1]) = 0 (Sum⊕Sum⊕…⊕Sum)⊕(nums[0]⊕…⊕nums[k]⊕…⊕nums[n−1])=0
再结合 SumSumSum 为原序列的异或和可得:
(Sum⊕Sum⊕…⊕Sum)⊕Sum=0,Sum≠0(Sum ⊕ Sum ⊕ … ⊕ Sum) ⊕ Sum = 0 , Sum \neq 0 (Sum⊕Sum⊕…⊕Sum)⊕Sum=0,Sum=0
至此,我们分析出当处于「后手必败态」时,去掉任意一个数值会满足上述式子。
根据「相同数值偶数次异或结果为 0」的特性,可推导出「后手必败态」会导致交回到先手的序列个数为偶数,由此推导后手操作前序列个数为奇数,后手操作前一个回合先手为偶数。
到这一步,我们推导出想要出现「后手必败态」,先手操作前的序列个数应当为偶数。
那么根据先手操作前序列个数为偶数(且异或和不为 0),是否能够推导出必然出现「后手必败态」呢?
显然是可以的,因为如果不出现「后手必败态」,会与我们前面分析过程矛盾。
假设先手操作前异或和为 XorXorXor(序列数量为偶数,同时 Xor≠0Xor \neq 0Xor=0),如果最终不出现「后手必败态」的话,也就是先手会输掉的话,那么意味着有 Xor⊕nums[i]=0Xor ⊕ nums[i] = 0Xor⊕nums[i]=0,其中 iii 为序列的任意位置。利用此性质,像上述分析那样,将每一项进行展开异或,会得到奇数个 XorXorXor 异或结果为 0,这与开始的 Xor!=0 矛盾。
由此推导出性质二:只需要保证先手操作前序列个数为偶数时就会出现「后手必败态」,从而确保先手必胜。
综上,如果序列 nums 本身异或和为 0,天然符合「先手必胜态」的条件,答案返回 True ;如果序列 nums 异或和不为 0,但序列长度为偶数,那么最终会出现「后手必败态」,推导出先手必胜,答案返回 True。
对于这两种题型的共同点为很容易想到dp,但是仔细想想会发现有点类似于井字棋,都存在先手必胜或必败的情况,具体描述引用如下,
百度搜索ICG博弈, ICG博弈是这类博弈的总括性理论. 这类博弈的核心特征在于, 只根据初始状态就可以判断双方的输赢情况
看对一些同学有帮助, 顺便把我自己的总结放在这里.
经典的Bash, Wythoff 以及Nim博弈问题, 都属于所谓的公平组合博弈(Impartial Combinatorial Games, ICG), ICG具有的的特征/性质如下(用局势(position)描述游戏中的一个状态):
两人参与, 轮流进行, 有限步内结束.
position空间只能划分为两个部分: 奇异局势(P-position)空间和非奇异局势(N-position)空间.
面对同一position, 两人具有相同的合法操作集合; 即选手的操作只与position有关而与选手无关.
对于任一P-position, 任意的合法操作都会使其变成N-position; 对于任一N-position至少存在一种合法操作使其变为P-position. (position空间的划分要满足此性质)
结束局势(E-position)定义为N-position空间中的一些, 面对它的选手赢; 或者定义为P-position空间中的一些, 面对它的选手输. (面对是指上一位选手操作完毕, 轮到当前选手, 而当前选手还未操作)
如果一个游戏满足上述性质, 即为ICG游戏. 那么由于P-position/N-position之间的这种转换关系(性质4), 我们就能, 只根据初始局势就可以判断双方的输赢情况. 通常判断先手是否赢, 先手赢的条件是初始局势为N-position.
启示: 面对一个博弈论(Game theory)问题, 我们可以大胆猜测它是一个ICG问题. 然后通过输赢关系找出一些N-position和P-position, 并尝试划分出各自的空间. 最后, 证明第4个性质. 当然在比赛中, 如果比较难证明, 我们可以直接通过提交代码来测试.
联系客服