完全平方数问题全解：动态规划、BFS与四平方定理

前阵子在刷题群里看到一个标题“力扣第84题完全平方数”。我第一反应是84 题不应该是“柱状图中最大的矩形”吗后来翻了几个整理版题单才发现不同平台的题号排序经常不一致有些地方把“完全平方数”提前放到了 84 这个位置。题号倒不是重点重点是这道题本身非常经典给你一个正整数 n返回最少能用几个完全平方数相加得到 n。所谓完全平方数就是 1、4、9、16 这样的整数平方。这道题在动态规划章节里几乎是必刷的第一梯队同时它还是一道非常自然的 BFS 例题。哪怕你刚开始刷题把这一题彻底吃透等于一次复习了动态规划、图的最短路径思考还顺带碰了一下数论里的四平方定理。这篇文章会从最直观的贪心思路开始讲再拆解 DP、BFS、数学公式三条主路线最后把常见错误和调试心得一起整理出来。1. 题目到底在问什么先别急着写代码1.1 题目描述重述给你一个正整数 n要求找到最少个数的完全平方数使它们的和等于 n。完全平方数可以重复使用。比如n 12可以写成 9 1 1 1用了 4 个数也可以写成 4 4 4用了 3 个数。答案是 3。n 13可以写成 9 4用了 2 个数。答案就是 2。n 18写成 16 1 1 需要 3 个数但 9 9 只需要 2 个数答案是 2。n 23最常见的凑法是 9 9 4 1答案其实是 4。很多人第一眼会把它和“整数拆分”混在一起但这里限制了一个条件拆出来的每个数必须是完全平方数。这其实和一个经典问题很像硬币找零。只不过硬币不是固定面额而是由 n 决定的所有平方数从 1 到不超过 n 的最大平方数都能用。这个“最少数量”非常关键。如果只问“能不能拆”那任何正整数都能用若干个 1 凑出来题目就失去意义了。刷题时一定要先抓住题眼不是找拆法而是找最少拆法。1.2 贪心会掉坑用一个反例把理由讲透我第一次做这道题时第一反应是“每次选能用的最大平方数不就行了”。这个思路叫贪心听起来很合理能用一个大的平方数为什么不先用大的结果马上被 n 12 打了脸。按贪心思路走12 能用的最大平方数是 9剩下 33 只能用 1 来凑所以得到 9 1 1 1一共 4 个但是 4 4 4 只需要 3 个。n 18 更明显贪心先选 16剩下 2得到 16 1 1一共 3 个而 9 9 只有 2 个。为什么贪心不行因为“当前这一步用掉最大平方数”并不会让全局最优。大的平方数有时会留下很难处理的余数或者让总个数变多。比如 12 使用 9 之后余数 3 是一个“很笨”的数字只能靠一堆 1 补齐反过来放弃 9 用两个 4反而干净利落。这个反例不是孤例。遇到带“最少数量”的拆解问题除非你能证明贪心选择性质否则都要往动态规划或者搜索方向想。2. 动态规划解法从“最后一步”反推2.1 状态设计和转移方程动态规划的第一步不是写代码而是定义状态。这里我定义dp[i] 表示凑出整数 i 所需的最少完全平方数个数。假设我们要凑 i那么最后一步一定选了某个完全平方数 j * j其中 1 j * j i。选完这个数之后剩下要凑的是 i - j * j。因为题目只要求数量最少所以dp[i] min(dp[i - j * j] 1)对所有满足 j * j i 的 j 取最小值。这句话翻译成大白话就是我不知道最后一个平方数是谁但我把所有可能的“最后一步”都试一遍谁留下的剩余部分更优就用谁。这个思路叫“从最后一步反推”是 DP 里最常用的建模方式。初始化时 dp[0] 0意思是一个数都不用就能凑出 0。其他 dp[i] 先设置成一个很大的数方便之后取 min。计算顺序从左到右因为 dp[i] 依赖的是下标更小的状态比如 i - 1、i - 4、i - 9 等这些都在 i 之前就已经算好了。2.2 参考代码C 版本#include vector #include climits class Solution { public: int numSquares(int n) { std::vectorint dp(n 1, INT_MAX / 2); dp[0] 0; for (int i 1; i n; i) { for (int j 1; j * j i; j) { dp[i] std::min(dp[i], dp[i - j * j] 1); } } return dp[n]; } };Python 版本def num_squares(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内层枚举所有不超过 i 的平方数 j * j把每种选择的代价都算一遍。2.3 边界条件和复杂度分析有几个细节值得注意dp[0] 0 是必须的。没有它dp[1] 就不知道从哪转移。dp 初始值不能是普通的 INT_MAX因为dp[i - j * j] 1会直接溢出。用 INT_MAX / 2 或者 float(inf) 都可以。内层循环条件是 j * j i不是 j * j i因为 n 本身如果是完全平方数直接返回 1 也应该由 dp 正确算出来。时间复杂度是 O(n * sqrt(n))。n 的约束通常在 10^4 以内内层最多跑约 100 次总共约 100 万次操作完全够快。空间复杂度 O(n)需要一个长度 n 1 的数组。3. BFS 解法把数字当成图上的节点3.1 为什么 BFS 能做动态规划不是唯一思路。这道题完全可以看成一张图上的最短路径问题从 n 出发每次操作就是减去一个完全平方数目标是到达 0。每走一步用掉一个平方数所以“最少步数”就是“最少平方数个数”。BFS 天然适合求最短路径因为它是按层扩散的先把 n 所有一步能到的数字走完再走两步能到的数字。第一次遇到 0 时当前层数就是答案。举个例子n 12 时第 0 层12第 1 层12 - 1 11、12 - 4 8、12 - 9 3第 2 层从 11 到 10、7、2从 8 到 7、4从 3 到 2第 3 层从 4 减 4 得到 0所以答案是 3这样一层一层向外扩不会出现“绕远路”的问题。和 DP 相比BFS 真正把“最少”这个语义直接变成了搜索层次。3.2 BFS 代码实现#include queue #include vector class Solution { public: int numSquares(int n) { std::queueint q; std::vectorint visited(n 1, 0); q.push(n); visited[n] 1; int level 0; while (!q.empty()) { int size q.size(); level; while (size--) { int cur q.front(); q.pop(); for (int j 1; j * j cur; j) { int next cur - j * j; if (next 0) return level; if (!visited[next]) { visited[next] 1; q.push(next); } } } } return -1; } };visited 数组非常重要。图只有 n 1 个节点如果不做标记同一个数字会被反复加入队列数据量稍大就直接超时。这里 visited[next] 1 的时机也应该在入队时立刻标记而不是出队时标记否则仍然会有大量重复入队。空间复杂度是 O(n)队列在最坏情况下可能存放很多节点但因为 visited 限制了状态总数整体可控。4. 数学解法四平方定理直接降维打击4.1 拉格朗日四平方定理如果你想在面试里秀一手数论知识可以记这个结论任何正整数都可以表示成不超过 4 个完全平方数之和。也就是说答案只可能是 1、2、3、4 其中之一。把范围直接缩小到四个选择后剩下的问题就变成了四个“判断题”。答案是不是 1检查 n 本身是不是完全平方数。答案是不是 2检查 n 能不能拆成两个平方数之和。答案是不是 4使用勒让德三平方定理的推论。如果上面都不是答案就是 3。勒让德三平方定理说的是一个正整数能表示成三个平方数之和当且仅当它不能被写成 4^a * (8b 7) 的形式。反过来如果 n 能写成 4^a * (8b 7)那么它不能用 3 个平方数表示答案至少要 4。结合四平方定理这种情况答案正好是 4。4.2 判定步骤和代码第一步判断 n 是否是完全平方数。是返回 1。第二步枚举第一个平方数判断 n - i * i 是否也是平方数。是返回 2。注意要先把第一步的“本身就是平方数”排除掉否则一个平方数会被错误判成两个数的组合。第三步把 n 里所有因子 4 除干净得到 m。如果 m % 8 7返回 4否则返回 3。为什么需要不停地除以 4因为定理里的形式是 4^a * (8b 7)而不是直接看 n % 8。比如 28 本身除以 8 余 4看起来不像特殊情况但 28 4 * 7属于 4^1 * (8 * 0 7)它其实不能用 3 个平方数表示。实战中漏掉这一步就会把 28 错判成 3。参考代码#include cmath class Solution { public: bool isSquare(int x) { int r static_castint(std::sqrt(x)); return r * r x; } int numSquares(int n) { if (isSquare(n)) return 1; for (int i 1; i * i n; i) { if (isSquare(n - i * i)) return 2; } int m n; while (m % 4 0) m / 4; if (m % 8 7) return 4; return 3; } };这个解法的平均复杂度低得夸张判断平方数和枚举二平方和都是 O(sqrt(n))除 4 的循环几乎可以忽略。空间 O(1)。当 n 的范围放大到 10^8 以上时这个方法的优势就非常明显。5. 三种解法对比刷题时到底怎么选5.1 时间、空间和适用场景整理成一个表解法时间复杂度空间复杂度核心思想适合场景动态规划O(n * sqrt(n))O(n)状态转移入门、理解无后效性BFS理论较高但数据量小很快O(n)图的最短路径换角度思考、加深搜索理解四平方定理O(sqrt(n))O(1)数论判定大数据量、面试加分动态规划最好写也最保险因为它不依赖数学结论只要状态转移写对就能过。BFS 适合用来解释“为什么最少”这个问题代码也不复杂但性能上限不如 DP 稳定尤其是状态没有标记好时容易超时。数学解法代码最短、速度最快但对定理不熟的人容易在边界条件上翻车。5.2 实际场景下的选择建议如果是在力扣上做这道题n 最大 10^4DP 已经绰绰有余。面试时如果时间紧张优先写 DP写完如果面试官追问“能不能更快”再抛出四平方定理这属于加分项。平时练习时我建议至少掌握两种解法DP 和 BFS。DP 能帮你建立“状态转移”的感觉BFS 能帮你把抽象题目可视化。数学解法可以当作兴趣或进阶但不要一开始就背结论否则遇到变体题会无从下手。如果题目要求改成“输出具体用了哪些平方数”DP 和 BFS 都能通过额外记录路径来还原数学解法反而很难直接给出构造方案。这也是为什么不要过度依赖数学技巧。6. 常见错误与调试实录6.1 典型错误速查表错误表现原因解决办法提交后答案偏大走了贪心路线每次选最大平方数改用 DP 或 BFS枚举所有可能DP 数组溢出导致结果异常dp 初始值用了 INT_MAX再加 1 溢出初始化为 INT_MAX / 2或用 long long忘记 dp[0] 0边界缺失i 1 时无法转移初始化时把 dp[0] 单独设为 0BFS 不断重复入队内存暴涨没有 visited 数组入队时立刻标记 visited数学解法把 28 算成 3只判断了 n % 8 7没有去掉因子 4先 while (m % 4 0) m / 4再判断 m % 8判断两个平方数时把 n 本身误判成 2没有先判断 n 是不是完全平方数第一步单独判断 isSquare(n)第七个容易踩的坑是 C 里直接用int r sqrt(x)时浮点误差可能导致平方根小 1。例如某些编译器里 sqrt(25) 得到 4.999999转成 int 就成了 4。更稳妥的写法是int r sqrt(x); if (r * r x) r;或者直接用整数二分判平方数。n 在 10^4 范围内我用直接转换没出过问题但如果你在更大数据范围内写建议加个修正。6.2 我自己踩过的坑我记得第一次用数学解法写这道题时自信满满地跑测试结果在 28 这个用例上挂了。当时我直接判n % 8 728 余 4于是返回 3。事实上 28 只能拆成 25 1 1 1 或者 16 9 1 1 1 这样的组合至少要 4 个平方数。后来把勒让德定理完整写出来才意识到“先除掉所有 4 因子”这一步不是可选项而是定理的一部分。还有一次用 BFS 时为了省代码没加 visited本地测试到 n 100 就开始明显变慢n 10000 直接跑不完。加上 visited 之后节点数最多一万个几毫秒就出结果。搜索题里“状态去重”不是优化而是必须品。7. 延伸思考和硬币找零、完全背包的关系这道题如果把平方数看成一堆“硬币面额”问题就变成了“用最少硬币凑出金额 n”这其实就是完全背包问题。常见写法是外层遍历物品、内层遍历容量但这道题由于硬币面额和 n 绑定直接在外层遍历 i、内层遍历 j 也能得到正确答案本质上是在做“朴素完全背包”。不过需要注意的是如果题目改成“输出所有可能拆法”或者“限制每个平方数最多用几次”转移状态就要相应扩展。比如限制次数时dp 数组可能需要增加一维或者把物品循环放在外层。力扣这道题不限制使用次数所以目前的 DP 写法已经足够。另一个经典问题是“整数拆分”把 n 拆成若干正整数之和求最大乘积。它和本题一样都是“把一个数拆成几个数”的 DP但拆分的对象不同、目标函数不同转移方程也完全不同。刷题时我会建议把这三题放在一起对比完全平方数、零钱兑换、整数拆分。它们放在一起能让“状态设计”这个概念理解得更透彻。最后说点个人感受我每次写这题都会先提醒自己“不要贪心”。一个简洁的数学结论可以秒杀题目但没有反例和证明支撑的结论只是空中楼阁。刷题最快乐的时刻往往不是 AC 的那一瞬间而是拿一个反例把自己的错误想法纠正过来的过程。把 DP、BFS、四平方定理都亲手跑一遍之后这道题才算真正吃透了。