LeetCode 464. 我能赢吗题目思路两个玩家轮流从 1 ~ maxChoosableInteger 中选一个未使用过的数字累加到总和先让总和 ≥ desiredTotal 的玩家获胜。问先手能否保证必胜。核心难点这是博弈 状态压缩问题。暴力枚举会爆炸必须记忆化。关键观察数字最多 20 个可以用一个 int 的二进制位表示哪些数字已被选状态压缩。当前累计总和 total 由 state 唯一确定已选数字之和所以记忆化只需按 state 存。必胜转移当前玩家选数字 i 时——· 若 total i target直接赢· 否则若 对手在下一状态必输!dfs(nextState)当前玩家也赢· 若枚举完所有选择都赢不了则当前玩家必输。剪枝· 若 maxChoosableInteger desiredTotal先手第一步直接达标必胜· 若所有数之和 desiredTotal谁都达不到目标先手判负。Java 代码状压 记忆化 DFSclassSolution{privateintm,target;privateint[]memo;// 0未计算, 1当前玩家必输, 2当前玩家必胜publicbooleancanIWin(intmaxChoosableInteger,intdesiredTotal){this.mmaxChoosableInteger;this.targetdesiredTotal;// 剪枝 1先手第一步就能达标if(mtarget)returntrue;// 剪枝 2所有数字之和都不够无人能赢先手判负if((long)m*(m1)/2target)returnfalse;memonewint[1m];returndfs(0,0);}/** * param state 二进制位标记已选数字第 i 位表示数字 i1 是否已选 * param total 当前累计和 * return 轮到当前玩家时是否能保证获胜 */privatebooleandfs(intstate,inttotal){if(memo[state]!0)returnmemo[state]2;for(inti0;im;i){if((state(1i))!0)continue;// 该数字已使用intnumi1;// 情况 1选完后立即达到目标 - 当前玩家赢if(totalnumtarget){memo[state]2;returntrue;}// 情况 2选完后对手必输 - 当前玩家赢if(!dfs(state|(1i),totalnum)){memo[state]2;returntrue;}}// 所有选择都赢不了含无数字可选的情况- 当前玩家输memo[state]1;returnfalse;}}复杂度分析· 时间复杂度O(m · 2^m)。状态数 2^m每个状态枚举 m 个数字。m ≤ 20约 2×10^7 次操作Java 中可过。· 空间复杂度O(2^m)。m 20 时 int[120] 约 4MB可接受。若想节省空间可把 int[] 换成 HashMapInteger, Boolean只存访问过的状态代价是常数更大。示例验证示例 1maxChoosableInteger 10, desiredTotal 11· 先手无论选 i1~10对手选 11-i 立即达到 11 → 先手必输· 返回 false ✓示例 2maxChoosableInteger 10, desiredTotal 0· 剪枝 110 0 直接返回 true目标为 0 时先手不选也算达标按题目约束此时先手直接胜出✓示例 3maxChoosableInteger 10, desiredTotal 1· 剪枝 110 1先手选 1 直接赢 → 返回 true ✓易错点易错点 说明状态定义 第 i 位代表数字 i10-indexed 转 1-indexed不要搞反total 是否需要进 memo 不需要。total 可由 state 唯一推出只按 state 记忆即可否则会重复计算浪费空间“无路可走的判定 循环结束仍未返回 true就返回 false等价于当前玩家输”sum 溢出 m*(m1)/2 在 m20 时只有 210不会溢出但养成用 long 的习惯剪枝遗漏 不加 sum target 的剪枝会产生大量无法分出胜负的无意义搜索