从能算到秒杀：完全平方数与最少数量的数学真相

LeetCode Hot 100 刷题笔记 · 第 15 篇如果说「跳跃游戏 II」是在教你什么时候不得不跳那279. 完全平方数​ 就是在考你最少能用几个平方数凑出一个整数这也是我第一次意识到有些动态规划其实是在替你跑 BFS。 题目速览LeetCode 279. 完全平方数中等给你一个整数n返回和为 n 的完全平方数的最少个数。完全平方数示例1 1 × 1 4 2 × 2 9 3 × 3 16 4 × 4示例输入n 12 输出3 解释12 4 4 4输入n 13 输出2 解释13 4 9 我的第一反应很危险看到“最少数量”直觉立刻冒出来BFSDP背包问题于是脑子里立刻出现dp[i] min(dp[i - k*k] 1)❌ 问题也很明显时间复杂度 O(n√n)面试如果再卡常数容易翻车没用到数学性质Hot100 不可能这么简单 真正解法一BFS最直观把这题看成一张图节点数值 0 ~ n边减去一个完全平方数求0 → n 的最短路径class Solution { public int numSquares(int n) { QueueInteger queue new LinkedList(); boolean[] visited new boolean[n 1]; queue.offer(0); visited[0] true; int steps 0; while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { int cur queue.poll(); for (int k 1; k * k n; k) { int next cur k * k; if (next n) return steps 1; if (next n) break; if (!visited[next]) { visited[next] true; queue.offer(next); } } } steps; } return -1; } }✅ 优点思路清晰❌ 缺点队列 访问数组略重 真正解法二DP工程最常用状态定义dp[i] 和为 i 的最少完全平方数个数状态转移dp[i] min(dp[i - k*k] 1)代码面试首选class Solution { public int numSquares(int n) { int[] dp new int[n 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] 0; for (int i 1; i n; i) { for (int k 1; k * k i; k) { dp[i] Math.min(dp[i], dp[i - k * k] 1); } } return dp[n]; } }复杂度时间复杂度O(n√n)空间复杂度O(n)✅ 稳定✅ 易写✅ 面试安全 真正解法三数学定理终极秒杀这是本题的灵魂。 拉格朗日四平方定理任意正整数最多可以表示为 4 个完全平方数之和进一步判断情况结论n 本身是完全平方数1n a² b²2n 4^k × (8m 7)4其他3代码面试加分项class Solution { public int numSquares(int n) { // 1 个平方数 if (isSquare(n)) return 1; // 2 个平方数 for (int i 1; i * i n; i) { if (isSquare(n - i * i)) return 2; } // 4 个平方数 int m n; while ((m 3) 0) m 2; if ((m 7) 7) return 4; // 剩下一定是 3 return 3; } private boolean isSquare(int x) { int r (int) Math.sqrt(x); return r * r x; } }✅ 时间复杂度O(√n)✅ 空间复杂度O(1)✅ 面试官直接点头 我学到的东西做完这题最大的感受是最少步数问题不一定是 DP也不一定是 BFS可能是数学。你不是在枚举答案而是在排除不可能。⚠️ 易错点总结误区正确做法上来就 DP先想想 BFS / 数学忽略平方数边界注意 k * k ≤ n不知道四平方定理面试前背下来 一句话总结完全平方数最少数量 BFS 最短路径 DP 最优子结构 数学定理排除法。 面试收尾建议直接背“这道题可以用三种方式解一是 BFS 建模最短路径二是 DP时间复杂度 O(n√n)三是利用拉格朗日四平方定理在 O(√n) 内完成。实际面试我会先用 DP 保底再用数学优化。”