博弈论??不不不,对于我这种菜鸡,就是经验派蒙思路的玄学问题
这篇的博弈论题目大致都是“两个人玩游戏 判断先手胜负” 主要还是从奇偶性入手 (毕竟两个人嘛)
权当给自己做个记录
(没有干货没有干货 话说也从来给不出干货 走过路过 有时间的 可以当个段落纠错题看 有指正的感激不尽)
系列从易到难 有四道题
1. 简单 1025. 除数博弈
2. 中等 486. 预测赢家
3. 中等 877. 石子游戏
4. 困难 810. 黑板异或游戏
除数博弈
原题链接
大致意思:给定一个数N
,从N
的因子里(但不包括N
)任选一个数(记为x
),将N
替换为N-x
,再由下一个玩家重复这个操作。当出现没法再选的情况(就是N = 1
),当前玩家判负,则另一玩家胜。
先手玩家在状态为N
时选一个数x
则状态变为N-x
且由后手玩家进行下一次选择
其实就相当于初始状态改为N-x
并把先手权让给了另一个玩家 原来的后手玩家变成了“初始状态为N-x
的先手玩家”
“原来的先手玩家”的必胜或必负态 其实就是对“原来的后手玩家”的必胜(负)态取反
用人话说
如果初始状态为N-x1
是先手必胜的 那么初始状态为N
的先手玩家就不能选择x1
否则另一个玩家作为新状态的先手必胜
如果出现初始状态为N-x2
是先手必败的 那么初始状态为N
的先手玩家只需要选择x2
就能保证自己必胜了 即初始状态为N
是先手必胜的
所以对于一个N
我们只需要找N-x
中有没有满足先手必败的状态 如果有则N是先手必胜 如果所有子状态都是先手必胜 那么N是先手必败的
DP解法
状态描述:记f[i]
表示当N=i
时先手是否必胜
属性:布尔值,true
OrFalse
状态计算:
已知f[1]
先手必败 (这就是DP的初始状态)
遍历N的所有因子(不包括自身) 直到出现f[N-x]==false
则f[N]=true
状态转移方程为 f[i] = !f[i-x1] || !f[i-x2] || !f[i-x3] ···
class Solution {
public boolean divisorGame(int n) {
boolean[] f = new boolean[n + 1];
f[1] = false;
for (int i = 2; i <= n; i++) { // 枚举初始状态
for (int j = 1; j < i; j++) { // 枚举因子
if (i % j == 0 && !f[i - j]) { // 是因子且 i-j是先手必败
f[i] = true; // 则i是先手必胜
break; // 找到任何一个先手必胜态就可以直接退出了
}
}
}
return f[n];
}
}
博弈论 玄学解法
拿捏不准的时候就多写几个样例找规律
1 没有可选的数了 先手必败
2 只能选1 则剩余1 另一个玩家必败 先手必胜
3 只能选1 则剩余2 另一个玩家必胜 先手必败
4 若选1 则剩余3 另一个玩家必败 若选2 则剩余2 另一个玩家必胜 先手必胜
5 只能选1 则剩余4 另一个玩家必胜 先手必败
6 选1余5则后手胜 选2余4则后手胜 选3余3则后手败 先手必胜
····
大胆假设 奇数时先手必败 偶数时先手必胜
怎么证明呢 (相信玄学)
这里只能提供个思路 (因为人菜)
奇数的因子只能是奇数 奇数-奇数=偶数 因此先手奇数 必然后手拿到偶数
偶数的因子可奇可偶 所以减完后的差也可奇可偶 因此先手偶数 可以决定后手拿到的是奇数还是偶数 只要保证后手拿到的奇数就能把决定权一直占有
两数相减 最终还是会减到状态为“已经枚举到的前几个数” 这时掌握偶数的只要保证“对手拿到奇数”就必胜 而拿到奇数的只能把偶数给另一个玩家 (但凡对面不放水就必输)
因此 先手拿到偶数就必胜 拿到奇数就必败
class Solution {
public boolean divisorGame(int n) {
return (n & 1) == 0;
}
}
预测赢家
原题链接
大致题意:给定一个数组,两个玩家每次只能从左右两端取,取完所有数,总和多的胜出(相等时先手胜出)。判断先手玩家是否必赢
区间DP解法
首先 判断总和谁比较多 等效于 判断先后手总和之差是否大于或等于0
状态表示:$f(i,j)$表示“选完区间$[i,j]$,先手对后手的最大净胜分(也就是先后手总和之差)”
状态计算:
- 当区间长度为1时($[i,i]$只有一个可选的数),净比分自然等于
nums[i]
- 当区间长度超过1时,对于一个区间 $[i,j]$,有两种情况(可供选择的只有两个数
nums[i]
和nums[j]
)- 先手(记为玩家A)选择
nums[i]
,则后手(记为玩家B)变为区间$[i+1, j]$的先手,根据状态表示的定义,玩家B在区间$[i+1, j]$的净胜分为$f(i+1, j)$(即B作为$[i+1,j]$的先手能取得比玩家A多$f(i+1,j)$的分数)。现在A选择了nums[i]
,那A作为$[i,j]$的先手,能取得的净胜分就是$nums[i] - f(i+1, j)$- 用数学的方式看也是可以的。$f(i+1,j)=sum_B-sum_A$,所以$f(i,j)=sum_A+nums[i]-sum_B=nums[i]-(sum_B-sum_A)=nums[i]-f(i+1,j)$
- 同理若先手选了
nums[j]
,则净胜分为$nums[j]-f(i,j-1)$
- 先手(记为玩家A)选择
- 综上,状态转移方程为$f(i,j) = max(nums[i] - f(i+1,j), nums[j] - f(i,j-1))$
典型的区间DP
第一层循环枚举长度
第二成循环枚举起点 从而根据长度计算得终点
根据状态转移方程求解
根据以上分析 最终结果(先手是否必胜)为$f(0,n-1) >= 0$
class Solution {
public boolean PredictTheWinner(int[] nums) {
int n = nums.length;
int[][] f = new int[n][n];
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (i == j) f[i][j] = nums[i];
else
f[i][j] = Math.max(nums[i]-f[i+1][j], nums[j]-f[i][j-1]);
}
}
return f[0][n - 1] >= 0;
}
}
这题的博弈论思路和下面那道同源 不过约束条件不够 没法用(或者是我修为还不够)
(会卡最后一个样例【0,0,7,6,5,6,1】)
等下一题写完再讲
石子游戏
原题链接
预测赢家的特例 加了限制条件 数必定有偶数个 且总数必定为奇数 当总和大于时胜出
DP解法完全相同 主要讲讲博弈论的思路 如果不是看了题解 我也确实没想到还能这么玩 这谁顶得住
数有偶数个 如果按索引(从0开始)的奇偶性分为两组 则有
组① 从索引0开始所有偶数索引位 本组最后一位是原数组的倒二位
组② 从索引1开始所有奇数索引位 本组最后一位是原数组的倒一位
因为题目规定总数必为奇数 所以组①、组②里必定有一个组是偏大的
现在有一个很关键的性质
先手开始选择 可选的是原数组的首位和最后一位 恰好是组①的首位 和 组②的最后一位
情况1:如果先手选择了组①的首位(原数组首位) 那么组②的首位也就暴露出来了 后手能选择的是组②的首位和最后一位 (是的 可选项都在组②里) 不管后手选了哪个 新暴露出来的必是组①最靠边的数 如果这是先手继续选择组①的数 那么就会再次出现刚才的局面 也就是说 如果先手一开始就选择了组① 那么他完全可以选完所有的组①
情况2:与上同理 如果先手选了组②的最后一位(原数组最后一位) 那么组①的最后一位(原数组倒二位)就暴露出来了 后手只能在组①里面选 也就是说 如果先手一开始就选择了组② 那么他完全可以选完所有的组②
因此如果组①是总和偏大的组 那么先手只需选择组①(也就是原数组首位) 就必胜
同理如果组②偏大 那么先手选择原数组最后一位 就必胜
所以 不管是哪个组偏大 先手只要都选那个组就必胜
那代码怎么实现?讲个笑话
class Solution {
public boolean stoneGame(int[] piles) {
return true;
}
}
回到上一题预测赢家的博弈论解法 (再强调一次 目前看来行不通的)
看似相差不多 只不过少了偶数个数的限制
总和是否奇数不重要 因为上一题“大于或等于”就胜出 所以当个数为偶数时 先手必胜
那如果是个数奇数呢
如果先手选了首尾任一个数 余下的数组成了偶数个 决定权在后手身上 而他必然可以选择总和更大的那个组
如果先手选的那个数加上剩余的那个组 大于或等于 后手选择的那个组
那么先手必胜
因此 只需要尝试 先手选择“首位”和“最后一位”的两种情况 如果出现上述情形 那么先手必胜
一切似乎很合理 但是为什么样例【0,0,7,6,5,6,1】会过不去呢
如果先手选0 $0 + (0 + 6 + 6) < (7 + 5 + 1)$
但若先手选1 $1 + (0 + 7 + 5) > (0 + 6 + 6)$ 必胜
我只考虑了 一个都选偶数索引组一个都选奇数索引组 的情况
却没有考虑有决定权的那个人 可能选到一半跳槽到另一个组去了 从而获得更大的总和
那为什么上一题(或者“偶数个数”情况)不用考虑跳槽的事 因为这是个充分不必要的关系
先手只选偏大的组 $\Rightarrow$ 先手必胜
先手必胜 $\not\Rightarrow$ 先手只选偏大的组
诚然 偶数个数下 也许可以跳槽 但没必要 因为从一而终也能赢
但奇数的时候不一样了 不跳就是死路一条
所以样例【0,0,7,6,5,6,1】 后手要怎么赢呢
1. 先手必选1 才有赢的可能 【0,0,7,6,5,6】
2. 后手选6 为什么? 你可以试试别的 [doge] 【0,0,7,6,5】
3. 先手只能选5 不然选0丢个5拿个6再丢个7 【0,0,7,6】
4. 这时候机智的后手该jump了 反手选一个0 闷声发大财【0,7,6】
5. 先手怎么办 选哪个都要丢7 0和6必定都是先手的 7只能送给后手
6. 所以最终先手得分$1+5+6+0=12$ 后手得分$6+0+7=13$ Emmmm..
下一题
黑板异或游戏
说实在的 求加法和 我还能DP相信科学 蒙状态方程苟一苟 (虽然没做过大概率蒙不出来) 但是异或和就原地阵亡了
原题链接
大致题意:还是一个非负数组 两个玩家轮流擦除其中的任意一个数 轮到某个玩家时 如果在擦除之前数组异或和等于0 那么该玩家胜出
怎么做呢?看官方题解去
如果一开始给的异或和就是0 那二话不说 先手已经胜出
否则我们再得找一个先手必胜的状态 但胜利的条件好像只有上面那种情形
那么换个方向 我们找后手必败的状态 后手必败就等效于先手必胜
后手什么必败呢 首先他当前的数组异或和必定不为0 即$Sum \neq 0$
其次因为必败 所以不管他从数组里选择哪个数来删除 都会导致新的$Sum^{\prime} = 0$
即删除前的数组为nums
别删除的数为nums[i]
数组长度为n
索引编号为1~n
则必败应满足 $Sum \neq 0$ 且 $Sum \oplus nums[1] = Sum \oplus nums[2] = \cdots = Sum \oplus nums[n] = 0$
尝试对所有的$Sum \oplus nums[i]$求异或和 因为各个子表达式为0 所有最终的异或和必为0
$(Sum \oplus nums[1]) \oplus (Sum \oplus nums[2]) \oplus \cdots \oplus (Sum \oplus nums[n]) = 0$
$\Rightarrow (Sum \oplus \cdots \oplus Sum) \oplus (nums[1] \oplus nums[2] \oplus \cdots \oplus nums[n]) = 0$
$\Rightarrow (Sum \oplus \cdots \oplus Sum) \oplus Sum = 0$ (前一个括号是$n$个$Sum$)
$\Rightarrow Sum \oplus \cdots \oplus Sum = 0$ (总的是$n + 1$个$Sum$)
再次重申$Sum$不等于0 否则当前状态直接就是后手获胜了
所以要使得$(n + 1)$个$Sum$异或和为0 那么$n+1$必然为偶数、$n$必然为奇数
而后手的数组长度$n$是通过先手去掉一个数字得到的 所以先手的数组长度为$(n+1)$ 是个偶数
因此要出现“后手必败” 必须满足先手的数组长度为偶数
那如果先手的数组长度为偶数 是否必然导致“后手必败”呢
反证法 如果先手偶数长度但最终不出现“后手必败”的状态 那么也就意味着先手的偶数长度数组会出现“必败”的状态
根据上面的推导 需要满足$Sum \neq 0$ 且 $Sum \oplus nums[1] = Sum \oplus nums[2] = \cdots = Sum \oplus nums[n] = 0$
化简到最后 $\Rightarrow Sum \oplus \cdots \oplus Sum = 0$ (总的是$n + 1$个$Sum$)
其中$n$作为数组长度是偶数 所以$(n+1)$是奇数
奇数个$Sum$异或得到0 $Sum$必然为0 这与前置条件足$Sum \neq 0$矛盾
因此 先手的数组长度为偶数 必然后出现“后手必败”
换言之 如果先手的数组长度是偶数 那么先手必胜
需要注意的是 这里先手偶数则后手必败 并不是说当前取出一个数 后手立刻进入“必败”的状态
而是说先手偶数 则后面再一次轮到它时必然还是偶数 后手奇数 则后面再一次轮到它时必然还是奇数
而偶数长度的先手数组 必然不会出现“必败”的状态 因此失败的只能是后手
class Solution {
public boolean xorGame(int[] nums) {
int sum = 0;
for (int num : nums) sum ^= num; // 计算初始异或和
return sum == 0 || (nums.length & 1) == 0; // 初始异或和为0 或 初始长度为偶数 则先手必胜
}
}
终于码完了 打个总结 这类博弈论算是简单的了 但是让我自己想 要是解的出当场磕豆腐跳茶杯
还是比较吃经验和思维 蒙思路的话 得从奇偶性入手 往往双方都足够聪明(那为什么要我个sb帮你解题) 所以中间过程多半不会给对方机会赢 所以决定胜负的是在初始状态和最终状态
比起来我更宁愿先蒙DP的思路
推一篇不错的题解 起码比我写的好得多得多
【宫水三叶の相信科学系列】运用「博弈论」分析「先手必胜态」序列具有何种性质
派蒙挺可爱的[ღ( ´・ᴗ・` )比心]