算法之博弈问题

文章目录

巴什博弈
- 292.Nim 游戏
尼姆博弈
斐波那契博弈
其他博弈
- 1025.除数博弈

博弈问题，就是双方之间的PK,关注的重点是谁先？以及A,B各自赢的条件
一般有数学问题，动态规划，搜索进行求解

巴什博弈

在这里插入图片描述

下面的这题Nim 游戏，就是巴什博弈，但是Nim Game 其实是指的是另外一题

292.Nim 游戏

在这里插入图片描述

思路分析：分析问题结束的情况，当最后轮到我的时候，剩余的石头的数目达到1,2,3的时候，我就是赢的，否则就是输的，那么怎么才能保证这种情况？我们可以可以观察到，通过n%4,就可以知道最后是否可以剩下对应的1,2,3个数目的石头

class Solution:def canWinNim(self, n: int) -> bool:# 由于每个人都是最优解，所以只要查看n是不是4的倍数即可if n % 4 == 0:return Falseelse:return True

尼姆博弈

在这里插入图片描述

斐波那契博弈

在这里插入图片描述

其他博弈

1025.除数博弈

在这里插入图片描述
官方题解

思路分析： 普通的思路我们可以知道，当n=1的时候，是False,n=2的时候是 True,所以我们可以采用类似于动态规划的思想进行遍历，我们可以从n=3开始，逐个向后面遍历到n,对于其中的i,我们再设置变量j从1到i-1进行遍历，当i%j==0的时候，我们只需判断 i-j 是否是False,如果有一个j满足 i-j 是False,那么爱丽丝就可以胜利，否则就是False

class Solution:def divisorGame(self, n: int) -> bool:# win = {2}los = {1}dp = [False]*(n+1)if n==1:return Falsedp[1] = Falsedp[2] = Truefor i in range(3,n+1):flag = 0for j in range(1,i):if i%j == 0:if (i-j) in los:flag=1breakif flag:dp[i] = Truewin.add(i)else:los.add(i)return dp[n]