8.4 KiB
tags, create time
| tags | create time | ||||
|---|---|---|---|---|---|
|
2026-05-16 19:00 |
84. 完全平方数（Perfect Squares）
[!quote] LeetCode 原题 · 中等 给你一个整数
n，返回和为 n 的完全平方数的最少数量。完全平方数是一个整数，其值等于另一个整数的平方。例如：1、4、9、16。
- 输入范围：
1 <= n <= 10⁴
题面
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
思路
第一步：把问题翻译成 DP 语言
[!question] 💡 思考 如果要凑出数字 n，你手里有 {1, 4, 9, 16, ...} 这些面额无限的"硬币"——这和哪类经典模型一致？
没错，这就是一个**「最小硬币数」版本**的完全背包问题：
- 物品集合：所有不超过 n 的完全平方数 → {1², 2², 3², ..., k²}，其中 k² ≤ n
- 每种物品可以无限使用
- 目标：选若干个物品使其总和恰好为 n，且物品个数最少
定义状态：
dp[i]= 和为 i 的完全平方数的最少数量
那状态转移呢？想象你已经凑到了 i，最后一步一定是从某个 i - j² 加上一个 j² 过来的：
dp[i] = min(dp[i - j*j]) + 1，对所有满足 j² ≤ i 的 j 取最小值
[!tip] 🧠 直观理解 画个例子：
dp[12]考虑最后加入的完全平方数可能是 1, 4, 9：
- 加 1：
dp[12] = dp[11] + 1- 加 4：
dp[12] = dp[8] + 1- 加 9：
dp[12] = dp[3] + 1三者取最小即可。
flowchart TD
subgraph "dp[12] 的状态转移"
A["dp[12]\n= min(...) + 1"] --> B["从 dp[11] + 1\n(最后加 1)"]
A --> C["从 dp[8] + 1\n(最后加 4)"]
A --> D["从 dp[3] + 1\n(最后加 9)"]
B --> E["dp[11]=4 → ans=5"]
C --> F["dp[8]=2 → ans=3 ✓最优"]
D --> G["dp[3]=3 → ans=4"]
end
style A fill:#e7f3ff,stroke:#3b82f6
style F fill:#dcfce7,stroke:#16a34a
第二步：确定边界条件
[!question] 💡 思考 dp[0] 应该是多少？为什么？
dp[0] = 0 ——和为 0 不需要任何完全平方数，答案是 0。这是所有状态的"空起点"。没有它，整个递推就没有根基。
第三步：自底向上填表
以 n = 12 为例完整走一遍——
| i | dp[i] 计算过程 | dp[i] |
|---|---|---|
| 0 | — | 0 |
| 1 | dp[0]+1 | 1 |
| 2 | dp[1]+1 | 2 |
| 3 | dp[2]+1 = dp[0]+1 | 2 |
| 4 | dp[3]+1, dp[0]+1 | 1 ← 本身就是平方数！ |
| 5 | dp[4]+1 = dp[1]+1 | 2 |
| 6 | dp[5]+1 = 3, dp[2]+1 = 3 | 3 |
| 7 | dp[6]+1 = dp[3]+1 | 3 |
| 8 | dp[7]+1 = dp[4]+1 | 2 ← 4+4 |
| 9 | dp[8]+1, dp[5]+1, dp[0]+1 | 1 ← 本身是平方数 |
| 10 | dp[9]+1 = dp[6]+1 | 3 |
| 11 | dp[10]+1 = dp[7]+1 | 3 |
| 12 | dp[11]+1 = dp[8]+1 = dp[3]+1 | 3 ← 4+4+4 |
flowchart LR
subgraph "填表示意 n=12"
A["i=0: 0"] --> B["i=1: 1"]
B --> C["i=2: 2"]
C --> D["i=3: 2"]
D --> E["i=4: 1 ★"]
E --> F["i=5: 2"]
F --> G["i=6: 3"]
G --> H["i=7: 3"]
H --> I["i=8: 2 ★"]
I --> J["i=9: 1 ★"]
J --> K["i=10: 3"]
K --> L["i=11: 3"]
L --> M["i=12: 3 ★答案"]
end
style A fill:#f3f4f6,stroke:#6b7280
style E fill:#fef3c7,stroke:#f59e0b
style I fill:#fef3c7,stroke:#f59e0b
style J fill:#fef3c7,stroke:#f59e0b
style M fill:#dcfce7,stroke:#16a34a
表中 ★ 标记表示该位置本身就是一个完全平方数，直接取 1。
代码提示
在动手写代码之前，想一想这些关键决策点：
[!question] 💡 思考 1 内层循环中，j 的范围应该是多少？怎么高效地枚举"所有不超过 i 的完全平方数"？
j 从 1 开始，只要 j*j ≤ i 就继续。这样 dp[i - j*j] 不会越界。每次循环只用一次乘法和一次比较，效率很高。
[!question] 💡 思考 2 Go 中没有内置的 min 对多个值取最小——你会怎么写？
可以先用一个变量 ans 初始化为无穷大（比如 i 本身，因为最坏情况是全用 1），然后在循环中逐个更新最小值。这样既简洁又避免了引入额外依赖。
技巧
剪枝：提前识别完全平方数
[!tip] ⚡ 小优化 如果 i 本身就是一个完全平方数（即存在某个 j 使得 j*j = i），那么
dp[i] = 1，可以直接跳过内层循环。
这个判断只需一行：if int(math.Sqrt(float64(i)))*int(math.Sqrt(float64(i))) == i { dp[i] = 1; continue }。虽然不影响渐近复杂度，但能加速一半以上的填充。
Lagrange 四平方定理（进阶）
[!abstract] 🔢 数论彩蛋：Lagrange 四平方定理 任意正整数都可以表示为不超过 4 个完全平方数之和。
这意味着答案永远 ∈ {1, 2, 3, 4}。配合 Legendre 三平方定理，可以做到 O(√n) 时间直接求解：
- 先消去因子 4（反复除以 4）
- 检查余数是否为
4ᵏ(8m+7)——如果是，答案就是 4- 否则尝试能否拆成两个平方数之和——能则是 2
- 其余情况都是 3
这个数学解法速度极快，但在面试中可能不容易当场推导出来。掌握 DP 方法已足够通过绝大多数场景。
| 方法 | 时间 | 空间 | 评价 |
|---|---|---|---|
| DP 填表（推荐） | O(n√n) | O(n) | 通用易懂，面试首选 |
| BFS | O(n√n) | O(n) | 第一层到达的答案必是最优，同样高效 |
| 数学法（四平方定理） | O(√n) | O(1) | 最快，但需记忆定理 |
代码
Go 语言实现
// numSquares returns the minimum number of perfect squares that sum to n.
func numSquares(n int) int {
// dp[i] = 和为 i 的完全平方数的最少数量
dp := make([]int, n+1)
for i := 1; i <= n; i++ {
// 初始化：最坏情况是全用 1 来凑
dp[i] = i
// 尝试每一种可能的最后一步 j*j
for j := 1; j*j <= i; j++ {
sum := dp[i-j*j] + 1
if sum < dp[i] {
dp[i] = sum
}
}
}
return dp[n]
}
[!summary] 💡 代码说明
- 外层循环：从左到右依次计算 dp[1], dp[2], ..., dp[n]，保证每个子问题在用到时已经被解决
- 内层循环：枚举所有可能的 j（1, 2, 3, ...），直到 j² > i 为止。每次考虑"最后一步加了 j²"这个选择
- 初始值 dp[i] = i：最坏情况是用 i 个 1 来凑（如 7 = 1+1+1+1+1+1+1）。内层循环一定能找到更优解
执行过程演示（n = 12）
i=1: j=1: dp[0]+1=1 → dp[1]=1 ← 1=1
i=2: j=1: dp[1]+1=2 → dp[2]=2 ← 2=1+1
i=3: j=1: dp[2]+1=3 → dp[3]=3 ← 3=1+1+1 (j=2时 4>3，停止)
i=4: j=1: dp[3]+1=4
j=2: dp[0]+1=1 → dp[4]=1 ← 4=4 ★
i=5: j=1: dp[4]+1=2
j=2: dp[1]+1=2 → dp[5]=2 ← 5=4+1
i=6: j=1: dp[5]+1=3
j=2: dp[2]+1=3 → dp[6]=3 ← 6=4+1+1
i=7: j=1: dp[6]+1=4
j=2: dp[3]+1=4 → dp[7]=4 ← 7=4+1+1+1
i=8: j=1: dp[7]+1=5
j=2: dp[4]+1=2 → dp[8]=2 ← 8=4+4 ★
i=9: j=1: dp[8]+1=3
j=2: dp[5]+1=3
j=3: dp[0]+1=1 → dp[9]=1 ← 9=9 ★
i=10: j=1: dp[9]+1=2
j=2: dp[6]+1=4
j=3: dp[1]+1=2 → dp[10]=2 ← 10=9+1
i=11: j=1: dp[10]+1=3
j=2: dp[7]+1=5
j=3: dp[2]+1=3 → dp[11]=3 ← 11=9+1+1
i=12: j=1: dp[11]+1=4
j=2: dp[8]+1=3 → dp[12]=3 ← 12=4+4+4
答案：dp[12] = 3 ✅
复杂度分析
- 时间复杂度：O(n√n) — 外层循环 n 次，内层循环最多 √n 次，总操作量约为 Σ(√i) ≈ (2/3)n^(3/2)
- 空间复杂度：O(n) — dp 数组占用 n+1 个整型空间
举一反三
这道题是 线性 DP + 枚举最后一项 的典型范式，同时也是「完全背包」思想的第一道落地应用：
- 81-爬楼梯 — 同样是线性 DP，但这里的"选择"不是固定两种，而是从一组可选值中选
- 83-打家劫舍 — 同样是逐状态递推，但约束不同（不能相邻 vs 无约束）
- LeetCode 322. 零钱兑换 — 完全背包的标准题，模板几乎一模一样（只是面额换成 coin value）
[!summary] 📌 本节要点
- 定义 dp[i] = 和为 i 的完全平方数最少个数
- 状态转移：dp[i] = min(dp[i - j²]) + 1，枚举所有 j² ≤ i
- 边界 dp[0] = 0，初始值 dp[i] = i（全用 1）
- 复杂度 O(n√n)，可以用 Lagrange 四平方定理做到 O(√n)