完全平方数如何用动态规划求最少数量？它和完全背包有什么关系？

简化版

完全平方数可以看成完全背包最少硬币问题：物品是 1,4,9,16...，每个平方数可以重复使用，目标容量是 n。定义 dp[i] 为组成 i 所需的最少平方数个数，转移为 dp[i] = min(dp[i], dp[i - square] + 1)。

详细版

先枚举所有不超过 n 的平方数，然后用一维 DP 求最小数量。初始化 dp[0]=0，其他位置设为较大值。对于每个金额 i，枚举平方数 s，只要 s <= i，就尝试从 i-s 转移过来。

这道题也可以按完全背包写：外层枚举平方数，内层容量正序遍历。时间复杂度通常是 O(n√n)，空间复杂度 O(n)。面试重点是解释“为什么平方数可以重复使用”，以及 dp[0]=0 的意义。

完整版教学

一、题目本质不是数学猜答案，而是最少组合数

给定 n=12，可以写成 4+4+4，所以答案是 3；给定 n=13，可以写成 4+9，答案是 2。题目问的是“最少使用多少个完全平方数”，这和零钱兑换的“最少硬币数”非常像。

平方数物品：1, 4, 9, 16, ...
目标容量：n
每个物品：可以重复使用
目标：物品数量最少

虽然背后有数论定理，但面试刷题里最稳的通用解法是动态规划。

二、状态定义为什么是“组成 i 的最少数量”

定义：

dp[i] = 组成整数 i 所需的最少完全平方数数量

这个定义能转移，是因为如果最后选了平方数 s，那么前面必须组成 i-s。只要知道 i-s 的最优答案，加上当前这个 s，就得到一种候选方案。

例如 i=12，可选平方数有 1,4,9：

选 1：dp[11] + 1
选 4：dp[8] + 1
选 9：dp[3] + 1

从这些候选里取最小值，就得到 dp[12]。

三、转移公式和初始化

初始化非常关键：

dp[0] = 0
dp[1..n] = +∞

转移公式：

for i from 1 to n:
    for square in squares:
        if square <= i:
            dp[i] = min(dp[i], dp[i - square] + 1)

dp[0]=0 表示组成 0 不需要任何数，它是所有转移的起点。如果没有它，dp[1] = dp[0]+1 就无法成立。

四、用 n=12 走一遍关键状态

平方数是 [1,4,9]。部分状态如下：

i	最优拆法	dp[i]
1	1	1
4	4	1
8	4+4	2
9	9	1
12	4+4+4	3

当算到 12 时，dp[8]+1=3 最优。dp[3]+1=4 对应 9+1+1+1，不是最少。

记忆钩子：最少数量类 DP，常见初始化是 dp[0]=0，其他位置先放大数。

五、完全背包视角怎么写

因为每个平方数可以重复使用，所以也可以把平方数当物品，把 n 当容量：

int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, n + 1);
    dp[0] = 0;
    for (int s = 1; s * s <= n; s++) {
        int square = s * s;
        for (int i = square; i <= n; i++) {
            dp[i] = Math.min(dp[i], dp[i - square] + 1);
        }
    }
    return dp[n];
}

容量正序遍历表示同一个平方数可以被重复使用。比如处理 4 时，dp[8] 可以在同一轮使用刚更新过的 dp[4]。

六、两种循环顺序的差异

按金额枚举和按物品枚举都能求最少数量，但它们表达的思路略不同。

写法	外层	内层	适合解释
直接 DP	金额 `i`	平方数 `s`	组成每个数的最优选择
完全背包	平方数 `s`	容量正序	物品可重复使用

这题求的是最少数量，不是排列数，所以两种写法答案一致。若是计数题，循环顺序就会影响“组合”还是“排列”。

七、常见误区与追问

误区：把容量倒序遍历。 倒序是 0-1 背包，会限制每个平方数只能用一次。
误区：忘记 dp[0]=0。 没有起点状态，所有加一转移都会断掉。
误区：用贪心每次取最大平方数。 12 取 9 后剩 3，总数 4；最优是 4+4+4，总数 3。
追问：时间复杂度是多少？ 平方数约有 √n 个，每个容量最多尝试这些数，所以是 O(n√n)。
追问：能不能用 BFS？ 可以，把数字看成节点，每次减一个平方数，最短层数就是答案。
追问：为什么完全背包内层正序？ 正序允许当前物品在同一轮继续被使用。

八、加强记忆

完全平方数要和零钱兑换绑定记：平方数是硬币，n 是金额，目标是最少硬币数。dp[i] 表示组成 i 的最少数量，最后拿一个平方数 s，前面就是 dp[i-s]。如果按背包写，看到“可重复使用”就用容量正序；如果按金额写，就逐个尝试所有不超过当前金额的平方数。

简化版

详细版