当前位置：首页 > news >正文

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

news 2026/5/28 22:35:40

解决方案

方法一：记忆化搜索 + 状态压缩

思路和算法

考虑边界情况，当所有数字选完仍无法到达 desiredTotal 时，两人都无法获胜，返回 false 。当所有数字的和大于等于 desiredTotal 时，其中一方能获得胜利，需要通过搜索来判断获胜方。

在游戏中途，假设已经被使用的数字的集合为 usedNumbers ，这些数字的和为 currentTotal 。当某方行动时，如果他能在未选择的数字中选出一个 i ，使得 i+currentTotal ≥ desiredTotal ，则他能获胜。否则，需要继续通过搜索来判断获胜方。在剩下的数字中，如果他能选择一个 i ，使得对方在接下来的局面中无法获胜，则他会获胜。否则，他会失败。

根据这个思想设计搜索函数 dfs ，其中 usedNumbers 可以用一个整数来表示，从低位到高位，第 i 位为 1 则表示数字 i 已经被使用，为 0 则表示数字 i 未被使用。如果当前玩家获胜，则返回 true ，否则返回 false 。为了避免重复计算，需要使用记忆化的操作来降低时间复杂度。

代码

Python3

class 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 >= desiredTot

Java

class Solution { Map<Integer, Boolean> memo = new HashMap<Integer, 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); } }

public class Solution { Dictionary<int, bool> memo = new Dictionary<int, 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]; } }