算法之 博弈问题

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

巴什博弈

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

292.Nim 游戏

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.除数博弈

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]

思路分析：对于这种问题，我们可以尝试先求解出前10种情况，看看有没有规律！！！

class Solution:def doesAliceWin(self, s: str) -> bool:# 统计原来的字符串中元音的个数# 如果个数为0，就输，否则就是赢的ser = {"a","e","i","o","u"}count = 0for i in s:if i in ser:count+=1return count!=0

石子游戏

877.石子游戏

877.石子游戏

思路分析：参照博主

参照博主的内容

class Solution:def stoneGame(self, piles: List[int]) -> bool:# 虽然我们一下子 通过分析可以知道，先手是永远胜利的n = len(piles)# dp[l][r] 定义为 区间[l,r]中，先手与后手的最大差值# 递推公式 dp[l][r] = max(piles[l-1]-dp[l+1][r],piles[r-1]-dp[l][r-1])# 其中 l 和 r 的范围都是 [1,n],所以要开的数组空间必须是 [0,n+1],不然就得特殊判断dp = [[0]*(n+2) for i in range(n+2)]# 我们从长度由1-n,左端点的范围[1,n]for i in range(1,n+1):for l in range(1,n-i+2):r = l+i-1dp[l][r] =  max(piles[l-1]-dp[l+1][r],piles[r-1]-dp[l][r-1])return dp[1][n]>0