刷 LeetCode Hot100 刷到第 67 题卡在 279 完全平方数上的人不在少数。这题表面是个数学题实际背后藏着动态规划、BFS、数论三条完全不同的解法每一条都够资格单独撑起一场面试追问。我第一次做的时候第一反应是贪心提交之后发现直接翻车后来老老实实把三种思路都写了一遍才真正搞懂这题想考什么。这篇文章就把 279 从暴力到最优完整拆一遍包括我在初始化、边界条件上踩过的坑给正在刷 Hot100 的朋友省点时间。1. 先看题目本身为什么最少个数比能不能凑成更考验人1.1 题目要求和两个经典样例LeetCode 279 的题干很短给定一个正整数 n找到若干个完全平方数比如 1、4、9、16使得它们的和等于 n返回和为 n 的完全平方数的最少数量。这里的完全平方数指k^2这种形式k 是正整数所以 1 也算在内。有了 1任何 n 都至少有一种分解问题从一开始就是有解的真正的难度全在最少这两个字。看两个经典例子n 12最少是 3 个12 4 4 4。有人会先想到 12 9 1 1 1那是 4 个不是最优。n 13最少是 2 个13 9 4。这两个例子放在一起能看出规律当 n 本身不含一个很大的平方因子时最优解往往不是先塞最大的平方数进去而是需要组合出更均衡的拆分。题目给的 n 上限是 10^4暴力枚举所有拆分方案完全不现实你必须先想清楚一件事——最少个数这个最优性指标到底更适合用什么方法表达出来。1.2 贪心为什么在这里翻车我估计不少人和我一样第一次看到这题会本能地这样想每次都挑不超过剩余值的最大的平方数然后继续凑。这个思路放在货币找零问题上很常见但在这道题里是错的。反例就是 n 12。贪心会先取 9剩余 3然后只能取三个 1总共得到 4 个平方数。可正确答案是 3 个。为什么会翻车因为平方数之间的大小关系不是倍数关系先拿一个大平方数会让剩余部分变得碎碎掉的部分往往需要更多小平方数来补齐总个数反而涨上去了。更本质的原因是完全平方数并不是一套任意金额都能用贪心凑出最优解的面额体系。贪心成立通常需要面额之间具备某种整除或可替代的性质而平方数完全不具备。所以凡是在题目里看到最少个数最小步数这类词我的经验是先把贪心放一边优先考虑动态规划或者搜索别在这个上面浪费时间。1.3 换个角度它就是一个完全背包再仔细看一眼约束每个完全平方数可以用一次也可以用很多次只要最后总和等于 n。这不就是经典的完全背包吗把物品看成1^2, 2^2, 3^2 ...物品的重量是平方数的值物品的代价是 1用了几个数就是几背包容量是 n。题目要求恰好装满背包并且让总代价最小。这个角度一旦建立起来解题思路就清楚了完全背包有固定的动态规划套路BFS 也可以从另一个视角套上去数学定理则是最后的杀手锏。2. 动态规划解法把平方数当成无限量物品2.1 状态定义和转移方程动态规划的关键是定义状态。设dp[i]表示凑出总和 i 所需的最少完全平方数个数目标是求dp[n]。显然dp[0] 0凑出 0 不需要任何数。对于任意i 0最后一个平方数一定是某个j*j其中1 j*j i。一旦确定了最后一个平方数剩下的问题就变成凑i - j*j这部分的最优解已经存在dp[i - j*j]里了。于是得到转移方程dp[i] min(dp[i], dp[i - j*j] 1) 其中 j 从 1 取到 sqrt(i)这个方程里的1代表的正是你选中的最后一个平方数。为什么枚举最后一个平方数是安全的因为任何一组分解都可以拆成最后一个数 前面的数前面的部分必然对应某个dp值枚举就能覆盖所有可能性。2.2 代码实现和初始化细节先看我日常提交的写法import math def numSquares(n: int) - int: # 初始化除了 dp[0] 0其余都先设成一个大数 dp [float(inf)] * (n 1) dp[0] 0 # 预先生成平方数列表避免在循环里反复开方 squares [i * i for i in range(1, int(math.sqrt(n)) 1)] for i in range(1, n 1): for sq in squares: if sq i: break dp[i] min(dp[i], dp[i - sq] 1) return dp[n]这里有两个细节第一次写很容易错第一dp数组除了dp[0]其余必须初始化为一个很大的数比如float(inf)。如果全初始化为 0min运算会永远取到 0转移方程直接失效。这是完全背包求最小值与求最大值在初始化上的核心区别求最大值通常初始化为 0 就够了求最小值必须考虑当前状态还不可达的情况。第二squares列表要包含1*1 1。有人生成平方数列表时会顺手从 2 开始写结果 n 是素数或者小数字时答案全错。1 在这里既是最小物品也是保证所有数字都能被凑出来的兜底。还有一种写法是不预生成列表直接在循环里用j*j判断import math def numSquares(n: int) - int: dp [float(inf)] * (n 1) dp[0] 0 for i in range(1, n 1): j 1 while j * j i: dp[i] min(dp[i], dp[i - j * j] 1) j 1 return dp[n]这种写法少一个列表但每个 i 都要从头开始计算 j 的限制代码更短理解起来也更直接。两种我都试过刷题阶段推荐第二种因为不依赖额外的math.sqrt面试时少一个浮点精度的话题。2.3 复杂度分析以及为什么它能过 10^4 却扛不住更大数据动态规划的时间复杂度是O(n * sqrt(n))外层 i 从 1 到 n内层 j 最多到sqrt(i)。空间复杂度是O(n)一个一维数组就够。n 最大是 10^4所以实际计算量大概是10000 * 100 1000000次量级任何一个在线评测系统都能轻松扛住。这也是 Hot100 里的题目常见量级。但这个复杂度放在更大的 n 上就不行了。如果面试官把 n 改成 10^9动态规划的数组根本开不下O(n * sqrt(n))的复杂度也完全不可接受。这时候答案就会落到后面的数学方法上BFS 虽然思路漂亮同样逃不掉O(n * sqrt(n))的量级。另外面试里如果追问能不能输出具体是哪几个平方数动态规划也能做额外维护一个prev数组记录每个dp[i]是从哪个i - j*j转移过来的最后从dp[n]往回回溯就能得到一组具体方案。这也是背包问题求方案的标准做法。3. BFS 解法把 n 到 0 的路径当图来走3.1 为什么这题能建模成最短路径动态规划是从 0 往上递推BFS 的思路则完全反过来从 n 出发每次可以减一个平方数比如从 12 可以一步走到 11、8、3分别减去 1、4、9然后继续往下走直到走到 0。这么看的话每个数字就是一个节点每次减平方数就是一条边边的长度是 1。问题变成了在这样一张状态图上从 n 到 0 的最短路径长度是多少。图上所有边的权重都是 1所以 BFS 天然就是正确且高效的搜索方式。第一次到达 0 时经过的层数就是最少需要的平方数个数。这个建模思路在算法题里很常见比如楼梯最少步数钥匙和房间这类题都是同一个套路状态是节点操作是边边权为 1 时用 BFS。3.2 代码实现以及 visited 数组为什么必须存在BFS 的实现我一般写成这样from collections import deque import math def numSquares(n: int) - int: q deque([n]) visited [False] * (n 1) visited[n] True step 0 while q: for _ in range(len(q)): cur q.popleft() if cur 0: return step for j in range(1, int(math.sqrt(cur)) 1): nxt cur - j * j if not visited[nxt]: visited[nxt] True q.append(nxt) step 1 return -1这里有一个必须加visited的原因状态图里存在回跳。比如从 5 可以减 1 到 4从 4 又可以减 1 到 3而从 3 再减 1 到 2或者从 4 减 4 直接到 0但如果没有visited搜索时会反复经过同一个数字队列会无限扩张理论上会超时。加了visited之后每个数字最多入队一次整个搜索规模就被限制在O(n)级别。visited数组的长度必须是n 1因为下标会取到 0。我第一次写的时候长度写成了 n结果nxt 0时直接越界这种低级错误很影响心态后来凡是开布尔数组都下意识加一。3.3 BFS 和 DP 的对比谁更快谁更好想BFS 和 DP 在这个问题上其实是在做同一件事BFS 是从 n 往 0 扩散DP 是从 0 往 n 递推。两者的时间复杂度量级差不多BFS 因为有visited剪枝在大多数实际数据下会更快一点但最坏情况仍然是O(n * sqrt(n))。面试时我应该选哪个我的习惯是如果面试官没有特别要求先讲 BFS因为它天然自带图论的建模训练解释起来故事感强如果面试官追问更优解法再引出 DP 和数学方法。理论上BFS 的层数概念对很多人来说比 DP 的状态转移更直观尤其是在现场推导的时候不容易卡壳。4. 数学方法四平方和定理带来的 O(sqrt(n)) 秒杀4.1 两条数论定理把答案范围缩到四种到这里为止的 DP 和 BFS 都能稳妥 AC但都不是最优解。这道题真正的尽头是数论。第一条定理叫四平方和定理每一个正整数都可以表示为至多四个整数的平方和。注意这里的整数可以包含 0所以至多四个意味着答案只可能是 1、2、3、4 中的一个。这就把搜索空间一下子压缩到了极小。第二条定理叫勒让德三平方和定理它更精确一个正整数能表示为三个整数的平方和当且仅当它不满足n 4^a * (8b 7)这种形式其中 a、b 都是非负整数。换句话说只有形如4^a * (8b 7)的数才一定需要 4 个平方数其他数用 3 个或更少就能搞定。两条定理合在一起判断逻辑就非常清晰了如果 n 本身就是完全平方数答案是 1。如果 n 能表示成两个平方数之和答案是 2。如果 n 满足4^a * (8b 7)的形式答案是 4。剩下的所有情况答案都是 3。4.2 三种情况的判断顺序和实现判断 1 和判断 2 都好理解关键是判断 4 的实现。怎么判断n 4^a * (8b 7)呢可以把 n 里的因子 4 一层层除掉比如先判断n % 4 0是则整体除以 4重复这个过程直到不能再除为止。剩下的数如果模 8 等于 7说明原 n 满足定理里的条件答案就是 4。完整实现如下import math def is_square(x: int) - bool: r math.isqrt(x) return r * r x def numSquares(n: int) - int: # 答案 1n 本身就是完全平方数 if is_square(n): return 1 # 答案 4不断去掉因子 4 后剩下部分模 8 等于 7 m n while m % 4 0: m // 4 if m % 8 7: return 4 # 答案 2枚举第一个平方数检查剩余部分是否也是平方数 for a in range(1, math.isqrt(n) 1): if is_square(n - a * a): return 2 # 剩下的情况就是答案 3 return 3这段代码的时间复杂度是O(sqrt(n))只发生在枚举两个平方数之和的那一步空间复杂度是O(1)。n 是 10^4 时几乎是瞬间出结果就算面试官把 n 改成 10^9这个解法依然能跑这也是它在面试里价值最大的原因。4.3 为什么判断 4 要放在判断 2 之前有人会问先判断 2 再判断 4 行不行逻辑上可以但我建议按上面代码的顺序写原因很简单判断 4 用的while m % 4会把 n 的值改掉如果你在它之后还想用原来的 n 做枚举就得先保存副本。代码里我用了m保存副本这样顺序就不容易出错。另外一个容易忽略的点完全平方数模 8 只可能是 0、1、4永远不可能是 7所以n 是完全平方数和n 模 8 等于 7这两种情况天然互斥答案 1 的判断放在最前面不会和答案 4 的判断冲突。5. 面试实战选型以及我提交 N 次后踩过的坑5.1 三种解法的指标对比三种解法不只是代码风格不同区别非常实在我整理了一张表解法时间复杂度空间复杂度适用场景面试推荐度动态规划O(n * sqrt(n))O(n)n 在 10^6 以内要求好理解高BFS最坏 O(n * sqrt(n))实际往往更快O(n)适合图论思维解释起来直观高数学定理O(sqrt(n))O(1)大数据量追求的极致复杂度中高取决于面试官喜好如果这是一道笔试编程题n 又只有 10^4我建议直接写 DP因为它最不容易出边界问题代码出错概率最低。如果这是一场算法面试我会先讲 BFS 再提数学定理因为面试官想看的往往不是你会背四平方和定理而是你能不能一步步把问题建模成图、转换成状态转移、最后再意识到数论结论。能讲出这个递进本身就说明你对这个题的理解比别人深一层。5.2 我实际提交时踩过的几个坑第一个坑是 BFS 里step的起点。如果用按层计数的写法step从 0 开始取到cur 0时返回step。这里最容易出错的是n本身是 1 的情况第一层从 1 出发走一步到 0第二次出队时cur 0step已经变成 1返回 1 才对。如果不小心把if cur 0写在入队之前可能直接漏掉这种情况。第二个坑是判断平方数时的浮点误差。int(math.sqrt(x))在 x 是 10^4 这种小数字时基本没问题但如果你后续拿它处理更大范围的变体题建议换成math.isqrt(x)它会返回整数平方根不存在浮点误差。我在处理n - a*a是否为完全平方数时最开始用int() ** 0.5判断某次跑变体题的时候出现过精度问题后来全换了isqrt才稳。第三个坑见得更频繁生成平方数列表时漏光 1。比如有人图省事写成[i*i for i in range(2, int(sqrt(n)) 1)]那 n 3 或者 n 5 这种必须靠 1 兜底的数字就永远算不对了。1 是这道题里最不起眼却最关键的数字因为它保证了任何 n 都有解。5.3 边界用例和可以继续扩展的方向跑几个小用例检查自己的实现n 1答案 1因为 1 本身就是完全平方数。n 2答案 2只有 1 1。n 3答案 31 1 1。n 4答案 1因为 4 2^2。n 7答案 4因为 7 4 1 1 1而且 7 模 8 等于 7正好落在答案 4 的判断规则里。n 12答案 34 4 4。如果面试进一步追问常见的变体有两个一是要求输出具体组合而非只求个数此时动态规划加回溯路径是最顺手的方向二是把完全平方数换成任意一组给定的正整数让你判断是否还是贪心问题这时候思路要立刻转到完全背包或者 BFS因为大部分面额体系下贪心都不成立。这些扩展并不是新题本质都是在考你能不能把最优性问题转移到你熟悉的算法模型上。写完三种方案回头看这道 LeetCode 279 会觉得很值一道题同时串起了贪心反例、动态规划、图搜索最短路径、数论定理四条主线。我个人实际刷题的建议是第一遍先用 DP 过掉拿到 AC 之后再强迫自己实现一遍 BFS最后再用数学方法做一次秒杀。这样刷一道题的收获比刷三题还大下次遇到类似的最少个数类问题你脑子里会同时浮现好几套方案选型也会从容得多。