254 lines
8.4 KiB
Markdown
254 lines
8.4 KiB
Markdown
|
---
|
|||
|
|
tags: [算法/动态规划, 基础DP, 完全背包, 数学/数论]
|
|||
|
|
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`
|
|||
|
|
>
|
|||
|
|
> 三者取最小即可。
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
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 |
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
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) 时间直接求解：
|
|||
|
|
>
|
|||
|
|
> 1. 先消去因子 4（反复除以 4）
|
|||
|
|
> 2. 检查余数是否为 `4ᵏ(8m+7)`——如果是，答案就是 4
|
|||
|
|
> 3. 否则尝试能否拆成两个平方数之和——能则是 2
|
|||
|
|
> 4. 其余情况都是 3
|
|||
|
|
|
|||
|
|
这个数学解法速度极快，但在面试中可能不容易当场推导出来。掌握 DP 方法已足够通过绝大多数场景。
|
|||
|
|
|
|||
|
|
| 方法 | 时间 | 空间 | 评价 |
|
|||
|
|
|------|------|------|------|
|
|||
|
|
| DP 填表（推荐） | O(n√n) | O(n) | 通用易懂，面试首选 |
|
|||
|
|
| BFS | O(n√n) | O(n) | 第一层到达的答案必是最优，同样高效 |
|
|||
|
|
| 数学法（四平方定理） | O(√n) | O(1) | 最快，但需记忆定理 |
|
|||
|
|
|
|||
|
|
## 代码
|
|||
|
|
|
|||
|
|
### Go 语言实现
|
|||
|
|
|
|||
|
|
```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] 📌 本节要点
|
|||
|
|
> 1. 定义 dp[i] = 和为 i 的完全平方数最少个数
|
|||
|
|
> 2. 状态转移：dp[i] = min(dp[i - j²]) + 1，枚举所有 j² ≤ i
|
|||
|
|
> 3. 边界 dp[0] = 0，初始值 dp[i] = i（全用 1）
|
|||
|
|
> 4. 复杂度 O(n√n)，可以用 Lagrange 四平方定理做到 O(√n)
|