leetcode岛屿数量（组合游戏系列1:）

leetcode岛屿数量（组合游戏系列1:）# TLE # Time Complexity: O(exponential) class Solution_BruteForce: def canWinNim(self n: int) -> bool: if n <= 3: return True for i in range(1 4): if not self.canWinNim(n - i): return True return False 以上的递归公式和代码很像fibonacci数的递归定义和暴力解法，因此对应的时间复杂度也是指数级的，提交代码以后会TLE。下图画出了当n=7时的递归调用，注意 5 被扩展向下重复执行了两次，4重复了4次。f(n) = ¬(f(n − 1) ∧

本系列，我们来看看在一种常见的组合游戏——回合制棋盘类游戏中，如何用算法来解决问题。首先，我们会介绍并解决搜索空间较小的问题，引入经典的博弈算法和相关理论，最终实现在大搜索空间中的Deep RL近似算法。在此基础上可以理解AlphaGo的原理和工作方式。 本系列的第一篇，我们介绍3个Leetcode中的零和回合制游戏，从最初的暴力解法，到动态规划最终演变成博弈论里的经典算法： minimax 以及 alpha beta 剪枝。

• 第一篇 Leetcode中的Minimax 和 Alpha Beta剪枝
• 第二篇: 一些组合游戏的理论
• 第三篇: 连接N个点 的OpenAI Gym GUI环境
• 第四篇: 蒙特卡洛树搜索（MCTS）和时间差分学习（TD learning）

Leetcode 292 Nim Game (简单)

简单题 Leetcode 292 Nim Game 。

你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。 你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例: 输入: 4

输出: false

解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

定义 f(n) 为有n个石头并采取最优策略的游戏结果， f(n)的值只有可能是赢或者输。考察前几个结果：f(1) = f(2) = f(3) = Win，然后来计算f(4)。因为玩家采取最优策略（只要有一种走法让对方必输，玩家获胜），对于4来说，玩家能走的可能是拿掉1块、2块或3块，但是无论剩余何种局面，对方都是必赢，因此，4就是必输。总的说来，递归关系如下：

f(n) = ¬(f(n − 1) ∧ f(n − 2) ∧ f(n − 3))

这个递归式可以直接翻译成Python 3代码

# TLE # Time Complexity: O(exponential) class Solution_BruteForce: def canWinNim(self n: int) -> bool: if n <= 3: return True for i in range(1 4): if not self.canWinNim(n - i): return True return False

以上的递归公式和代码很像fibonacci数的递归定义和暴力解法，因此对应的时间复杂度也是指数级的，提交代码以后会TLE。下图画出了当n=7时的递归调用，注意 5 被扩展向下重复执行了两次，4重复了4次。

292 Nim Game 暴力解法调用图 n=7

我们采用和fibonacci一样的方式来优化算法：缓存较小n的结果以此来计算较大n的结果。 Python 中，我们可以只加一行lru_cache decorator，来取得这种动态规划效果，下面的代码将复杂度降到了 O(N)。

RecursionError: maximum recursion depth exceeded in comparison n=1348820612 # Time Complexity: O(N) class Solution_DP: from functools import lru_cache @lru_cache(maxsize=None) def canWinNim(self n: int) -> bool: if n <= 3: return True for i in range(1 4): if not self.canWinNim(n - i): return True return False

再来画出调用图：这次5和4就不再被展开重复计算，图中绿色的节点表示缓存命中。

292 Nim Game 动归解法调用图 n=7

但还是没有AC，因为当n=1348820612时，这种方式会导致栈溢出。再改成下面的循环版本，可惜还是TLE。

# TLE for 1348820612 # Time Complexity: O(N) class Solution: def canWinNim(self n: int) -> bool: if n <= 3: return True last3 last2 last1 = True True True for i in range(4 n 1): this = not (last3 and last2 and last1) last3 last2 last1 = last2 last1 this return last1

由此看来，AC 版本需要低于 O(n) 的算法复杂度。上面的写法似乎暗示输赢有周期性的规律。事实上，如果将输赢按照顺序画出来，就马上得出规律了：只要 n mod 4 = 0 就是输，否则赢。原因如下：当面临不能被4整除的数量时 4k i (i=1 2 3)，一方总是可以拿走i个，将4k留给对手，而对方下轮又将返回不能被4整除的数，如此循环往复，直到这一方有1 2 3 个，最终获胜。

输赢分布

最终AC版本，只有一句语句。

# AC # Time Complexity: O(1) class Solution: def canWinNim(self n: int) -> bool: return not (n % 4 == 0)

Leetcode 486 Predict the Winner (中等)

中等难度题目： Leetcode 486 Predict the Winner .

给定一个表示分数的非负整数数组。 玩家1从数组任意一端拿取一个分数，随后玩家2继续从剩余数组任意一端拿取分数，然后玩家1拿，……。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。 给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1: 输入: [1 5 2]

输出: False

解释: 一开始，玩家1可以从1和2中进行选择。 如果他选择2（或者1），那么玩家2可以从1（或者2）和5中进行选择。如果玩家2选择了5，那么玩家1则只剩下1（或者2）可选。 所以，玩家1的最终分数为 1 2 = 3，而玩家2为 5。 因此，玩家1永远不会成为赢家，返回 False。

示例 2: 输入: [1 5 233 7]

输出: True

解释: 玩家1一开始选择1。然后玩家2必须从5和7中进行选择。无论玩家2选择了哪个，玩家1都可以选择233。 最终，玩家1（234分）比玩家2（12分）获得更多的分数，所以返回 True，表示玩家1可以成为赢家。

对于当前玩家，他有两种选择：左边或者右边的数。定义 maxDiff(l r) 为剩余子数组 [l r] 时，当前玩家能取得的最大分差，那么

对应的时间复杂度可以写出递归式，显然是指数级的：

采用暴力解法可以AC，但运算时间很长，接近TLE边缘 (6300ms)。

# AC # Time Complexity: O(2^N) # Slow: 6300ms from typing import List class Solution: def maxDiff(self l: int r:int) -> int: if l == r: return self.nums[l] return max(self.nums[l] - self.maxDiff(l 1 r) self.nums[r] - self.maxDiff(l r - 1)) def PredictTheWinner(self nums: List[int]) -> bool: self.nums = nums return self.maxDiff(0 len(nums) - 1) >= 0

从调用图也很容易看出是指数级的复杂度

486 Predict the Winner 暴力解法调用图 n=4

上图中我们有重复计算的节点，例如[1-2]节点被计算了两次。使用 lru_cache 大法，在maxDiff 上仅加了一句，就能以复杂度

和运行时间 43ms AC。

# AC # Time Complexity: O(N^2) # Fast: 43ms from functools import lru_cache from typing import List class Solution: @lru_cache(maxsize=None) def maxDiff(self l: int r:int) -> int: if l == r: return self.nums[l] return max(self.nums[l] - self.maxDiff(l 1 r) self.nums[r] - self.maxDiff(l r - 1)) def PredictTheWinner(self nums: List[int]) -> bool: self.nums = nums return self.maxDiff(0 len(nums) - 1) >= 0

动态规划解法调用图可以看出节点 [1-2] 这次没有被计算两次。

486 Predict the Winner 动归解法调用图 n=4

Leetcode 464 Can I Win (中等)

类似但稍有难度的题目 Leetcode 464 Can I Win 。难点在于使用了位状态压缩。

在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到 100 的玩家，即为胜者。 如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？ 例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。 给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？ 你可以假设 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。

示例： 输入： maxChoosableInteger = 10 desiredTotal = 11

输出： false

解释： 无论第一个玩家选择哪个整数，他都会失败。 第一个玩家可以选择从 1 到 10 的整数。 如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。 第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利. 同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

# AC # Time Complexity: O:(2^m*m) m: maxChoosableInteger class Solution: from functools import lru_cache @lru_cache(maxsize=None) def recurse(self status: int currentTotal: int) -> bool: for i in range(1 self.maxChoosableInteger 1): if not (status >> i & 1): new_status = 1 << i | status if currentTotal i >= self.desiredTotal: return True if not self.recurse(new_status currentTotal i): return True return False def canIWin(self maxChoosableInteger: int desiredTotal: int) -> bool: self.maxChoosableInteger = maxChoosableInteger self.desiredTotal = desiredTotal sum = maxChoosableInteger * (maxChoosableInteger 1) / 2 if sum < desiredTotal: return False return self.recurse(0 0)

上面的代码算法复杂度为 O(m*2^m)，m是maxChoosableInteger。由于所有状态的数量是2^m，对于每个状态，最多会尝试m走法。

首发于 MyEncyclopedia 公众号，欢迎大家关注。