完全平方数

拿 n＝12 试贪心：先减最大的 9，剩 3，再减 1、1、1，一共 4 枚。但 4+4+4 只要 3 枚。贪心错了，因为最大平方数不一定在最优解里。

想凑出 x，就枚举最后放下的那枚平方数 sq；放下它之前已经凑好 x−sq，所以 dp[x] = dp[x−sq] + 1，对所有可用的 sq 取最小。

地基 · dp[0]=0，其余设成无穷：凑出 0 不需要任何平方数，所以 dp[0]＝0。其余位置先填无穷，表示「还没找到办法」。

先用 sq=1 铺底 · 每格都能 +1 凑成：第一枚硬币只用 1：凑 4 就放四个 1，dp[4]＝4。全用 1 一定能凑出来，但枚数最多——这是保底解，后面更大的平方数来把它压小。

换 sq=4 进场 · dp[4] 被压到 1：现在轮到平方数 4。凑 4 时，回头看 dp[4−4]＝dp[0]＝0，再 +1 就是一枚 4。比原来的 4 枚 1 好太多，dp[4] 从 4 降到 1。

sq=4 继续 · dp[8] 由 dp[4] 接力：这是 sq＝4 这一轮从左往右刚算到 dp[8] 的中途快照：凑 8 时回看 dp[8−4]＝dp[4]＝1，再加一枚 4，就是 4+4＝两枚。它右边的 dp[9..12] 还停在上一轮全用 1 的旧值（9、10、11、12），扫描的指针还没走到，等会儿才轮到它们被压小。

灵魂帧 · dp[12] 在两条路里挑小的：凑 12 时回看 dp[12−4]＝dp[8]＝2，再加一枚 4，就是 4+4+4＝三枚。dp[12] 从 12 直接掉到 3。这就是动态规划的核心动作：站在大问题的肩膀上回看小问题。

最后 sq=9 再扫一遍 · 还能更小吗：最后一枚平方数 9 上场：dp[9] 被压到 1。再试 dp[12] 走 9 这条＝dp[3]+1＝4，没有 3 好，所以 dp[12] 守住 3。扫完所有平方数，dp[12]＝3 就是答案。

完全背包的灵魂：站在 x，枚举最后一枚平方数 sq，答案就是 dp[x−sq]+1 取最小。记住这句，零钱兑换、组合总和都是它。

雷区实演 · 贪心在 n=12 真的会输：贪心先抓最大的 9，剩下 3 只能补三个 1，合计 4 枚。DP 不迷信最大值，老老实实比较两条路，选出 4+4+4 这条只要 3 枚。这就是为什么这题必须用 DP。

面试追问：三个高频追问：循环能否交换、数学最优解、BFS 视角。把它们讲成自己的话，面试就稳了。

迁移阶梯：完全平方数是「完全背包求最少个数」的原子题。把硬币换成任意面额就是零钱兑换 322，把 min 换成计数就是组合总和 IV。想吃透这一类，去专题里连刷，卡住就问小欧或开通关训练。

边界三连：三个边界：最小的 n＝1、恰好是平方数的 n＝4、需要两枚拼的 n＝13。跑通它们，主流程和初始化就都对了。