题目描述
思路解析
一句话答案：LeetCode 279 完全平方数是完全背包型动态规划：把平方数当成可无限使用的硬币，dp[x] 表示凑出 x 的最少枚数，枚举最后一枚平方数 j²，取 dp[x - j²] + 1 的最小值。贪心先减最大平方数会出错（12 贪成 9+1+1+1 四枚，最优 4+4+4 三枚），必须 DP，时间 O(n·√n)、空间 O(n)。
完全平方数这道题在问什么
给一个正整数 n，用若干个完全平方数（1、4、9、16……）加起来恰好等于 n，同一个平方数可以用任意多次，求最少要用几个。换个说法：市面上有面额为各个平方数的硬币、每种无限供应，问凑出 n 元最少要几枚硬币——这一转译直接把它归进了「凑数求最少个数」这一类问题。
为什么贪心先拿最大的平方数会错
最诱人的直觉是贪心：每次减去不超过余额的最大平方数。拿 n = 12 试一下就露馅了——贪心先减 9，剩 3 只能用三个 1，共 9+1+1+1 四枚；而最优解是 4+4+4，只要三枚。贪心失败的原因在于「本步拿最大」和「总枚数最少」之间没有必然联系：一枚大硬币可能把余额切成很碎的形状，逼后面用一堆小硬币收尾。局部最优推不出全局最优，就得老老实实把所有选择都比一遍——这正是动态规划的活。
dp 状态怎么定义，为什么枚举最后一枚
定义 dp[x] 为凑出 x 所需的最少平方数枚数，起点 dp[0] = 0——凑 0 不需要任何硬币，其余先记无穷大表示还没找到办法。
转移的切入点是枚举「最后一枚」：任何一种凑出 x 的方案，总有最后加上去的那枚平方数 j²，把它拿掉，剩下的部分凑的是 x - j²。关键在于剩下的部分也必须是最优的——如果凑 x - j² 存在更少枚数的方案，直接替换进来就能让整体更少，与最优矛盾。所以 dp[x] = min(dp[x - j²] + 1)，j² 取遍所有不超过 x 的平方数。这种「大问题的最优解由小问题的最优解拼成、且怎么凑出 x - j² 不影响后续」的性质，就是动态规划要求的无后效性。对 n = 12，最终 dp[12] = 3。
为什么说这题就是完全背包，和零钱兑换什么关系
「若干种面额、每种可以无限使用、恰好凑出目标值、求最少件数」是完全背包的标准形态，本题的面额恰好是所有平方数而已。把平方数换成任意给定的硬币面额，就是 LeetCode 322 零钱兑换，两题共用同一套 dp 骨架。识别出这层骨架的价值在于：以后再遇到「无限供应 + 凑目标 + 求最值」的题，可以直接套这个转移，不必从头推。
复杂度怎么数，哪些边界容易翻车
外层从 1 算到 n，内层枚举的平方数 j² 不超过 x，也就是 j 最多到 √x，所以时间是 O(n·√n)；空间是一维数组 O(n)。
三个易错点：一是 dp[0] 必须设成 0，它是整条递推链的地基，设错全表跟着错；二是内层循环条件是 j·j <= x 而不是 j <= x，只能减真正的平方数；三是其余位置的初值要设成无穷大，否则 min 会被没意义的 0 干扰。此外别忘了 1 也是平方数，任何 n 都一定凑得出来，不存在无解情形。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条转移：枚举「最后一枚平方数」，回头看那枚之前的最优解再 +1，取所有选择里最小的。
建一行 dp 表，下标就是要凑的数 0…12。凑出 0 不需要任何平方数，dp[0]=0；其余先记 ∞ 表示「还没找到办法」。
算 dp[1]：枚举最后一枚平方数（1）。dp[1−1]+1 = dp[0]+1 = 1。蓝色就是各条来路 dp[1−j²]。
所有选择里 1 最小，填进 dp[1]。选的最后一枚是 1，它之前的 dp[0]=0，再 +1 就是 1。
算 dp[2]：枚举最后一枚平方数（1）。dp[2−1]+1 = dp[1]+1 = 2。蓝色就是各条来路 dp[2−j²]。
所有选择里 2 最小，填进 dp[2]。选的最后一枚是 1，它之前的 dp[1]=1，再 +1 就是 2。
算 dp[3]：枚举最后一枚平方数（1）。dp[3−1]+1 = dp[2]+1 = 3。蓝色就是各条来路 dp[3−j²]。
所有选择里 3 最小，填进 dp[3]。选的最后一枚是 1，它之前的 dp[2]=2，再 +1 就是 3。
算 dp[4]：枚举最后一枚平方数（1、4）。dp[4−1]+1 = dp[3]+1 = 4， dp[4−4]+1 = dp[0]+1 = 1。蓝色就是各条来路 dp[4−j²]。
所有选择里 1 最小，填进 dp[4]。选的最后一枚是 4，它之前的 dp[0]=0，再 +1 就是 1。
算 dp[5]：枚举最后一枚平方数（1、4）。dp[5−1]+1 = dp[4]+1 = 2， dp[5−4]+1 = dp[1]+1 = 2。蓝色就是各条来路 dp[5−j²]。
所有选择里 2 最小，填进 dp[5]。选的最后一枚是 1，它之前的 dp[4]=1，再 +1 就是 2。
算 dp[6]：枚举最后一枚平方数（1、4）。dp[6−1]+1 = dp[5]+1 = 3， dp[6−4]+1 = dp[2]+1 = 3。蓝色就是各条来路 dp[6−j²]。
所有选择里 3 最小，填进 dp[6]。选的最后一枚是 1，它之前的 dp[5]=2，再 +1 就是 3。
算 dp[7]：枚举最后一枚平方数（1、4）。dp[7−1]+1 = dp[6]+1 = 4， dp[7−4]+1 = dp[3]+1 = 4。蓝色就是各条来路 dp[7−j²]。
所有选择里 4 最小，填进 dp[7]。选的最后一枚是 1，它之前的 dp[6]=3，再 +1 就是 4。
算 dp[8]：枚举最后一枚平方数（1、4）。dp[8−1]+1 = dp[7]+1 = 5， dp[8−4]+1 = dp[4]+1 = 2。蓝色就是各条来路 dp[8−j²]。
所有选择里 2 最小，填进 dp[8]。选的最后一枚是 4，它之前的 dp[4]=1，再 +1 就是 2。
算 dp[9]：枚举最后一枚平方数（1、4、9）。dp[9−1]+1 = dp[8]+1 = 3， dp[9−4]+1 = dp[5]+1 = 3， dp[9−9]+1 = dp[0]+1 = 1。蓝色就是各条来路 dp[9−j²]。
所有选择里 1 最小，填进 dp[9]。选的最后一枚是 9，它之前的 dp[0]=0，再 +1 就是 1。
算 dp[10]：枚举最后一枚平方数（1、4、9）。dp[10−1]+1 = dp[9]+1 = 2， dp[10−4]+1 = dp[6]+1 = 4， dp[10−9]+1 = dp[1]+1 = 2。蓝色就是各条来路 dp[10−j²]。
所有选择里 2 最小，填进 dp[10]。选的最后一枚是 1，它之前的 dp[9]=1，再 +1 就是 2。
算 dp[11]：枚举最后一枚平方数（1、4、9）。dp[11−1]+1 = dp[10]+1 = 3， dp[11−4]+1 = dp[7]+1 = 5， dp[11−9]+1 = dp[2]+1 = 3。蓝色就是各条来路 dp[11−j²]。
所有选择里 3 最小，填进 dp[11]。选的最后一枚是 1，它之前的 dp[10]=2，再 +1 就是 3。
算 dp[12]：枚举最后一枚平方数（1、4、9）。dp[12−1]+1 = dp[11]+1 = 4， dp[12−4]+1 = dp[8]+1 = 3， dp[12−9]+1 = dp[3]+1 = 4。蓝色就是各条来路 dp[12−j²]。
所有选择里 3 最小，填进 dp[12]。选的最后一枚是 4，它之前的 dp[8]=2，再 +1 就是 3。
最右 dp[12]=3 就是凑出 12 的最少平方数个数——正好是 4+4+4 这三枚。
三个边界先想清：恰好是平方数→1；否则至少要两枚拼。
两个高频追问，把模板迁移讲清楚。
参考代码
def numSquares(n: int) -> int: dp = [0] + [float("inf")] * n for x in range(1, n + 1): j = 1 while j * j <= x: dp[x] = min(dp[x], dp[x - j * j] + 1) j += 1 return dp[n]复杂度
- 时间：O(n·√n)，外层 n 个数，内层最多 √n 个平方数
- 空间：O(n)，一维 dp 数组
易错点
面试追问把动画讲成自己的话
追问为什么不能用贪心？
追问和零钱兑换 322 什么关系？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最小路径和
LeetCode 64 · 中等 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题