完全平方数 · Perfect Squares
完全背包 DP · 数论坍缩用最少的「平方块」凑出 n。诀窍不是套公式，而是让每个数都试一遍「最后一块剥哪个平方」，再取最少 —— 而且贪心拿最大块会翻车。
题目：用最少的平方块拼出 n
题目绿 已定稿 · 蓝 当前 i · 紫 候选会跳回的子问题 · · 尚未计算
Go 解法 · 与状态同步
高亮行: 11func numSquares(n int) int {2 dp := make([]int, n+1)3 for i := 1; i <= n; i++ {4 dp[i] = i // 上界：全用 1，最多 i 块5 for j := 1; j*j <= i; j++ {6 dp[i] = min(dp[i], dp[i-j*j]+1)7 }8 }9 return dp[n]10}
第 6 行就是核心： dp[i] = min(dp[i], dp[i-j*j]+1) —— 内层 j 枚举每种平方块，外层 i 正序保证「完全背包」可重复取用。
机器状态 · 这一帧的全部变量
不变量
因为正序遍历且每种平方块可重复取用，填 dp[i] 时所有更小的 dp[i−s²] 都已是最终值，所以「子问题已解决」这条前提永远成立 —— 这正是完全背包的底气。
执行轨迹 · 每个 dp[i] 的最优一块
点击行跳转| i | 候选 (剥 s → +1) | 最优剥块 | dp[i] | 陷阱 |
|---|---|---|---|---|
| 1 | 1→1 | 1 | 1 | · |
| 2 | 1→2 | 1 | 2 | · |
| 3 | 1→3 | 1 | 3 | · |
| 4 | 1→4 4→1 | 4 | 1 | · |
| 5 | 1→2 4→2 | 4 | 2 | · |
| 6 | 1→3 4→3 | 4 | 3 | · |
| 7 | 1→4 4→4 | 4 | 4 | · |
| 8 | 1→5 4→2 | 4 | 2 | · |
| 9 | 1→3 4→3 9→1 | 9 | 1 | · |
| 10 | 1→2 4→4 9→2 | 9 | 2 | · |
| 11 | 1→3 4→5 9→3 | 9 | 3 | · |
| 12 | 1→4 4→3 9→4 | 4 | 3 | ⚠ |
反例沙盒 · 自己输入 n，看贪心怎么翻车
12 不是完全平方数、不形如 4^a(8b+7)、也写不成两平方和，于是 3 块。
设计哲学 · 看穿结构，O(n√n) 坍缩成 O(√n)
DP 是「不懂问题结构时的通用打法」。但数论早有答案 —— 拉格朗日四平方定理：任何正整数都能写成至多 4 个平方数之和。所以这道题的答案 永远只可能是 1 / 2 / 3 / 4，搜索空间小到离谱。配合 勒让德三平方定理（n 形如 4^a(8b+7) 才需要 4 块），就能用一串 O(√n) 的判断直接报答案， 整张 dp 表都省了。
面试 30 秒答题模板
平方数能无限次取用，要凑出 n 用最少块，是完全背包式 DP。定义 dp[i] 为凑出 i 的最少平方数个数，dp[0]=0。转移时枚举最后一块平方 s²≤i： dp[i] = 1 + min(dp[i − s²])。外层 i 正序、内层 j 从 1 到 √i，时间 O(n·√n)、空间 O(n)，答案 dp[12] = 3。进阶可提一句：由拉格朗日四平方定理答案恒 ≤ 4，能用 O(√n) 数论判定直接秒杀。
常见误区 · 别再翻车
- 用贪心拿最大平方块见大就拿会把余数推到难拼的数。如 n=12：先抢 9 只能 9+1+1+1=4 块，而 4+4+4 才 3 块。必须枚举每种最后一块，不能只看眼前最大。
- dp[0] 没设成 0dp[0]=0 是递推地基：当 i 本身是完全平方数时，dp[i] = dp[0]+1 = 1 才成立。若把 dp[0] 当成 ∞ 或漏掉，所有完全平方数的答案都会算错。
- 内层循环写成 j ≤ i 而非 j*j ≤ i枚举的是平方块 j*j，不是 j 本身。条件应是 j*j ≤ i，剥掉的值是 j*j。写成 j ≤ i 会把非平方数也当积木，结果全错。
迁移练习 · 同一套「枚举最后一块」骨架
把「平方块」换成任意硬币面额，求凑出 amount 的最少硬币数。转移完全一样：dp[i] = 1 + min(dp[i − coin])。LC279 就是面额固定为平方数的特例。
把「平方块」换成词典里的单词，dp[i] 从 bool（能否拆）出发：dp[i] = OR(dp[i − len(word)] 且 s[i−len:i] 命中词典)。同样是「枚举最后一段」。
同样枚举最后一块，但把 min+1 换成累加：dp[i] += dp[i − num]。从「最少几块」迁移到「有几种凑法」，体会同一套「枚举最后一步」的骨架。