完全平方数：最后一刀切在哪个平方
1、4、9 这些数可以重复用。凑 i 的时候枚举最后一刀是几的平方，剩下的查更小的格子。从 0 一层层加上平方数，层数同样是答案。
dp[0]=0。对每个 i，枚举 k²≤i，取 dp[i−k²]+1 的最小值。dp[n] 就是最少个数。也可以从 0 做 BFS，每步加上一个平方数，第一次到达 n 的层数即答案。时间 O(n√n)，空间 O(n)。
给你正整数 n，要把它写成若干完全平方数的和，每个平方数都能用多次，求最少需要几个。完全平方数就是 1、4、9、16 这种某整数的平方。
主例 n = 12。12=4+4+4，三个 2²，这是最少的；12=9+1+1+1 要用四个，更差。答案是 3。
四平方和定理保证任意自然数都能写成最多四个平方数之和，所以一定有解。本文要回答：为什么只要枚举「最后一刀」，主例 12 的表上每个格子怎么来，以及把平方数当成边时 BFS 的层数为什么等于这张表。
枚举最后一刀切在哪个平方
第一直觉是能用大的就用大的：12 先切 9，剩下 3，再三个 1，一共四个。主例已经说明贪心不是最少。另一种做法是搜索所有拆法，12 还能拆成六个 1 加一个 4 等等，分支很多，且子问题反复出现：剩下 8 的最少个数会被算许多遍。
缺的是按规模从小到大填表。问「凑出 i 最少几个平方数」，记作 dp[i]。最后一刀一定是某个 k²，且 k² ≤ i，剩下 i−k² 的最少个数已经算过，所以 dp[i] = min(dp[i−1], dp[i−4], dp[i−9], …) + 1。i 本身全用 1 来凑，最多 i 个，可以当初始上界。dp[0]=0：什么都不切，零个平方数凑出 0。
每个平方数能用多次，因为剩下的子问题还可以再切同样的 k²。这和「物品无限、恰好装满」的完全背包是同一张转移式，物品体积是 1、4、9…，价值一律 1，目标是件数最少。
用手走主例到 12。1、2、3 只能用 1，dp 是 1、2、3。i=4 第一次能切 4，dp[0]+1=1，演示标出 dp[4]=1。5、6、7 在 4 后面补 1，是 2、3、4；i=8 切两个 4，dp[4]+1=2。
i=9 切 9，dp[9]=1，演示第二帧。10、11 是 2、3。i=12 能切的平方是 1、4、9，对应看 dp[11]、dp[8]、dp[3]，分别是 3、2、3，加一后最小是 3。整表 [0,1,2,3,1,2,3,4,2,1,2,3,3]，答案 3，对应 4+4+4。
同一件事也可以用层序搜索来数。从 0 出发，每一步给当前数加上一个平方数，第一次走到 n 的步数就是最少个数。主例第 1 层到 1、4、9，第 2 层出现 8=4+4，第 3 层才出现 12=8+4，和 dp[12]=3 一致。n 不大时两种写法都常用；中间值要反复用时，填 dp 更直接。
不要把「最少个数」写成「有多少种拆法」。12 的拆法不止一种，题目只要 3 这个数目。初始化若全写成 0 而不是上界，min 会一直停在 0，整表废掉。转移必须用已经算完的更小下标，所以 i 从 1 递增到 n，不能倒着填。
完全背包视角平方数可重复取，体积是 k²，求恰好凑满 n 的最少件数。dp 与 BFS 问的是同一个最短件数：一个按容量递增填，一个按件数递增扩。四平方和定理只保证有解，不代替填表。
Go：DP 填表
func numSquares(n int) int {dp := make([]int, n+1)for i := range dp { dp[i] = i } // 全用 1² 兜底for i := 1; i <= n; i++ {for k := 1; k*k <= i; k++ {if dp[i-k*k]+1 < dp[i] {dp[i] = dp[i-k*k] + 1}}}return dp[n]}
1dp[i]=i 是全用 1 的上界，也让 dp[0] 保持 0。不要初始化成 0，min 会失效。
2内层 k 只走到 k*k≤i。主例 i=12 比较的是减去 1、4、9 之后的格子，最小加一得 3。
3每个 i 最多试 √i 个平方，总时间 O(n√n)。返回的是个数，不是具体拆法。
总结
枚举最后一刀 k²，或从 0 BFS 按层加平方数。主例 12 用三个 4。
- 贪心先切 9 会得到 4 个数，不是最少。要比较所有合法的最后一刀。
- 主例 dp[4]=1、dp[9]=1、dp[12]=min(3,2,3)+1=3，对应 4+4+4。
- BFS 第几层第一次到达 n，就是 dp[n]。本题要最少个数，不要数拆法种数。