企业官网建设流程全解析

前阵子在刷题群里看到一个标题：“力扣第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，剩下 3；
• 3 只能用 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::vector<int> 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::queue<int> q; std::vector<int> 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_cast<int>(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 时间、空间和适用场景

整理成一个表：

动态规划最好写也最保险，因为它不依赖数学结论，只要状态转移写对就能过。BFS 适合用来解释“为什么最少”这个问题，代码也不复杂，但性能上限不如 DP 稳定，尤其是状态没有标记好时容易超时。数学解法代码最短、速度最快，但对定理不熟的人容易在边界条件上翻车。

5.2 实际场景下的选择建议

如果是在力扣上做这道题，n 最大 10^4，DP 已经绰绰有余。面试时如果时间紧张，优先写 DP；写完如果面试官追问“能不能更快”，再抛出四平方定理，这属于加分项。

平时练习时我建议至少掌握两种解法：DP 和 BFS。DP 能帮你建立“状态转移”的感觉，BFS 能帮你把抽象题目可视化。数学解法可以当作兴趣或进阶，但不要一开始就背结论，否则遇到变体题会无从下手。

如果题目要求改成“输出具体用了哪些平方数”，DP 和 BFS 都能通过额外记录路径来还原，数学解法反而很难直接给出构造方案。这也是为什么不要过度依赖数学技巧。

6. 常见错误与调试实录

6.1 典型错误速查表

第七个容易踩的坑是 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 == 7，28 余 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、四平方定理都亲手跑一遍之后，这道题才算真正吃透了。