经典算法题之我能赢吗（二）

解决方案方法一记忆化搜索 状态压缩思路和算法考虑边界情况当所有数字选完仍无法到达 desiredTotal 时两人都无法获胜返回 false 。当所有数字的和大于等于 desiredTotal 时其中一方能获得胜利需要通过搜索来判断获胜方。在游戏中途假设已经被使用的数字的集合为 usedNumbers 这些数字的和为 currentTotal 。当某方行动时如果他能在未选择的数字中选出一个 i 使得 icurrentTotal ≥ desiredTotal 则他能获胜。否则需要继续通过搜索来判断获胜方。在剩下的数字中如果他能选择一个 i 使得对方在接下来的局面中无法获胜则他会获胜。否则他会失败。根据这个思想设计搜索函数 dfs 其中 usedNumbers 可以用一个整数来表示从低位到高位第 i 位为 1 则表示数字 i 已经被使用为 0 则表示数字 i 未被使用。如果当前玩家获胜则返回 true 否则返回 false 。为了避免重复计算需要使用记忆化的操作来降低时间复杂度。代码Python3class Solution: def canIWin(self, maxChoosableInteger: int, desiredTotal: int) - bool: cache def dfs(usedNumbers: int, currentTotal: int) - bool: for i in range(maxChoosableInteger): if (usedNumbers i) 1 0: if currentTotal i 1 desiredTotal or not dfs(usedNumbers | (1 i), currentTotal i 1): return True return False return (1 maxChoosableInteger) * maxChoosableInteger // 2 desiredTotJavaclass Solution { MapInteger, Boolean memo new HashMapInteger, Boolean(); public boolean canIWin(int maxChoosableInteger, int desiredTotal) { if ((1 maxChoosableInteger) * (maxChoosableInteger) / 2 desiredTotal) { return false; } return dfs(maxChoosableInteger, 0, desiredTotal, 0); } public boolean dfs(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotal) { if (!memo.containsKey(usedNumbers)) { boolean res false; for (int i 0; i maxChoosableInteger; i) { if (((usedNumbers i) 1) 0) { if (i 1 currentTotal desiredTotal) { res true; break; } if (!dfs(maxChoosableInteger, usedNumbers | (1 i), desiredTotal, currentTotal i 1)) { res true; break; } } } memo.put(usedNumbers, res); } return memo.get(usedNumbers); } }C#public class Solution { Dictionaryint, bool memo new Dictionaryint, bool(); public bool CanIWin(int maxChoosableInteger, int desiredTotal) { if ((1 maxChoosableInteger) * (maxChoosableInteger) / 2 desiredTotal) { return false; } return DFS(maxChoosableInteger, 0, desiredTotal, 0); } public bool DFS(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotal) { if (!memo.ContainsKey(usedNumbers)) { bool res false; for (int i 0; i maxChoosableInteger; i) { if (((usedNumbers i) 1) 0) { if (i 1 currentTotal desiredTotal) { res true; break; } if (!DFS(maxChoosableInteger, usedNumbers | (1 i), desiredTotal, currentTotal i 1)) { res true; break; } } } memo.Add(usedNumbers, res); } return memo[usedNumbers]; } }复杂度分析时间复杂度O(2*n × n)其中 n maxChoosableInteger 。记忆化后函数 dfs 最多调用 O(2*n) 次每次消耗 O(n) 时间总时间复杂度为 O(2*n×n) 。空间复杂度O(2*n)其中 n maxChoosableInteger 。搜索的状态有 O(2*n) 种需要消耗空间记忆化。