本文主要是介绍【脑筋急转弯】leetcode—1025.除数博弈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。
思路1：
两个玩家皆以最佳状态参与游戏，表明两人皆会做出 有利于自己的选择。
若N为偶数，则其因子可能为偶，也可能为奇；
若N为奇数，则其因子一定为奇数。
而赢得的游戏的关键，在于谁先得到2。
Alice先手开局，
若N初始为奇数，则Bob得到的一定是偶数。为最先得到2，Bob接下来所选的x一定为奇数（因为偶-奇=奇）。则所得N序列，即为：奇->偶->奇->偶->奇->偶->…
若N为初始为偶数，为最先得到2，Alice接下来所选的x一定为奇数（因为偶-奇=奇）。则所得N序列为：偶->奇->偶->奇->偶->…
最终问题可简化为：若两人均以最佳状态参与：当N初始为偶数，则alice一定赢；当N初始为奇数，则alice一定输。
解答1：
class Solution:def divisorGame(self, N: int) -> bool:return N%2==0
思路2：
动态规划
解答2：
class Solution:def divisorGame(self, N: int) -> bool:# dp[i] 表示当前数字 i 的时候先手是处于必胜态还是必败态，true 表示先手必胜，false 表示先手必败#从前往后递推，根据我们上文的分析，枚举 i 在 (0,i) 中 因数 j，看是否存在 dp[i−j] 为必败态即可if N==1:return Falseif N==2:return Truedp=[False]*(N+1)dp[1]=Falsedp[2]=Truefor i in range(3,N+1):for j in range(1,i):if i%j==0 and dp[i-j]==False:dp[i]=Truereturn dp[N]这篇关于【脑筋急转弯】leetcode—1025.除数博弈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
