完全平方数

给你一个整数 n，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方。换句话说，它的值等于一个整数自乘的积。
例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

• 1 <= n <= 10^4

动态规划：

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, n + 1);
        dp[0] = 0;

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j * j <= i; j++)
            {
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }
};

核心思想

这题要求的是：用尽可能少的完全平方数凑出 n。

一个直接想法是枚举所有拆分方式，比如：

12 = 1 + 1 + ... + 1
12 = 4 + 4 + 4
12 = 9 + 1 + 1 + 1

但是拆分方式很多，暴力枚举会重复计算大量相同的子问题。

这题最关键的观察是：

如果最后选择的一个完全平方数是 j * j，那么前面剩下的部分一定是 i - j * j。

也就是说，想知道组成 i 的最少完全平方数数量，可以先枚举最后一个完全平方数。

如果最后一个数是 j * j，那么答案就是：

组成 i - j * j 的最少数量 + 1

所以我们只要把所有可能的 j * j 都试一遍，取最小值即可。

这就是动态规划。

状态定义

定义：

dp[i] 表示和为 i 的完全平方数的最少数量。

题目要求的答案就是：

dp[n]

因为任意正整数 i 都可以由 i 个 1 组成，所以答案一定存在，并且：

dp[i] <= i

因此代码中可以把初始值设为 n + 1，表示一个暂时不可能达到的较大值。

递推公式推导

现在考虑如何求 dp[i]。

假设组成 i 的方案中，最后一个完全平方数是：

j * j

那么这个完全平方数必须满足：

j * j <= i

去掉最后这个 j * j 之后，剩下的和就是：

i - j * j

如果要让整体数量最少，那么剩下这部分也应该用最少数量的完全平方数组成，也就是：

dp[i - j * j]

再加上最后选的这个 j * j，总数量就是：

dp[i - j * j] + 1

由于最后一个完全平方数可能是 1、4、9、16 等，只要不超过 i 都可以尝试。

所以状态转移公式为：

dp[i] = min(dp[i], dp[i - j * j] + 1)

其中：

1 <= j 且 j * j <= i

换成完整形式就是：

dp[i] = min(dp[i - 1 * 1] + 1, dp[i - 2 * 2] + 1, dp[i - 3 * 3] + 1, ...)

一直枚举到 j * j <= i 为止。

边界情况

当 i = 0 时，不需要任何完全平方数就能组成 0。

所以：

dp[0] = 0

这是整个递推的起点。

例如计算 dp[4] 时，可以选择最后一个完全平方数为 4：

dp[4] = dp[4 - 4] + 1 = dp[0] + 1 = 1

这正好表示：

4 = 4

只需要 1 个完全平方数。

为什么可以这样递推

因为任何一个组成 i 的合法方案，最后一个数一定是某个完全平方数。

假设最后一个数是 j * j，那么它前面的所有数加起来一定等于：

i - j * j

也就是说，所有合法方案都可以按照“最后一个完全平方数是什么”来分类。

分类之后：

• 如果最后一个数是 1，前面需要组成 i - 1
• 如果最后一个数是 4，前面需要组成 i - 4
• 如果最后一个数是 9，前面需要组成 i - 9
• 依次类推

对于每一类方案，最后一个数已经固定为 1 个完全平方数。
剩下部分要想让总数量最少，就必须使用对应子问题的最优解。

因此，当前问题的最优解一定来自这些子问题最优解中的最小值。

完全平方数可以重复使用吗

可以。

题目只要求若干个完全平方数的和等于 n，并没有限制每个完全平方数只能用一次。

例如：

12 = 4 + 4 + 4

这里 4 被使用了三次。

在动态规划转移中，这一点体现在：

dp[i - j * j]

本身可能已经使用过 j * j。
现在再加上一个 j * j，仍然是合法的。

所以这道题本质上也可以理解成“完全背包”的最少数量问题：

• 物品：所有不超过 n 的完全平方数
• 每个物品：可以无限次使用
• 目标：凑出总和 n
• 代价：使用的完全平方数数量尽可能少

不过本题用一维动态规划按和递推，会更直观。

正确性证明

我们证明：动态规划算法返回的 dp[n] 等于和为 n 的完全平方数的最少数量。

归纳基础

当 i = 0 时，不需要选择任何完全平方数就可以得到和 0。

所以最少数量是 0，即：

dp[0] = 0

这与定义一致，因此基础情况正确。

归纳假设

假设对于所有小于 i 的非负整数 x，dp[x] 都已经正确表示和为 x 的完全平方数最少数量。

也就是说，对于任意 0 <= x < i，dp[x] 都是正确的最优解。

归纳推导

现在考虑 dp[i]。

任意一个和为 i 的完全平方数组合，最后一个完全平方数一定可以写成：

j * j

其中：

j * j <= i

去掉这个最后的 j * j 后，剩余部分的和是：

i - j * j

因为 j * j >= 1，所以：

i - j * j < i

根据归纳假设，dp[i - j * j] 已经是组成 i - j * j 的最少数量。

因此，如果最后一个完全平方数固定为 j * j，那么这一类方案中最少需要：

dp[i - j * j] + 1

个完全平方数。

算法枚举了所有满足 j * j <= i 的完全平方数，所以它不会漏掉任何可能作为最后一个数的选择。

因此，算法得到的：

min(dp[i - j * j] + 1)

不会大于真实最优解。

另一方面，算法每次用来更新 dp[i] 的值，都是由一个合法方案构造出来的：

1. 先用 dp[i - j * j] 个完全平方数组成 i - j * j
2. 再加上一个完全平方数 j * j

这样得到的总和一定是：

i - j * j + j * j = i

所以算法得到的每一个候选值都对应一个真实合法的拆分方案。
因此，算法得到的结果不会小于真实最优解。

综合两点可知，算法求出的 dp[i] 恰好等于组成 i 的完全平方数最少数量。

由数学归纳法可知，对所有 0 <= i <= n，dp[i] 都正确。

所以最终返回的 dp[n] 正确。

举例理解

以 n = 12 为例。

初始化：

dp[0] = 0

逐步递推：

所以：

dp[12] = 3

答案是 3。

再看 n = 13：

可以选择最后一个完全平方数 9：

dp[13] = dp[13 - 9] + 1 = dp[4] + 1 = 2

对应：

13 = 4 + 9

所以答案是 2。

复杂度分析

外层循环枚举 i，范围是 1 到 n。

内层循环枚举所有满足：

j * j <= i

的 j，最多有 sqrt(i) 个。

因此总时间复杂度是：

O(n * sqrt(n))

额外使用了一个长度为 n + 1 的 dp 数组，所以空间复杂度是：

O(n)