279. 完全平方数

题目链接（中等）

题目描述

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

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

数据范围：

• 1 <= n <= 10^4

示例

示例 1：

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

示例 2：

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

核心思路

把问题转成：用最少的完全平方数凑出 n。

完全平方数有 1, 4, 9, 16, ...，每个数可以重复使用，求凑出 n 的最少个数。

这本质是一个完全背包问题：物品是各个完全平方数，每个物品可以无限取，求装满容量 n 的最小物品数。

两种解法：

1. 动态规划：dp[i] 表示凑出 i 的最少个数，逐个枚举使用的最后一个完全平方数；
2. 数学（四平方和定理）：任何正整数最多用 4 个完全平方数表示，分类讨论答案 1、2、3、4 的情况，直接判定。

---

方法一：动态规划

思路及解法

定义 dp[i] 为「凑出整数 i 所需的最少完全平方数个数」。

转移思路：枚举最后一个使用的完全平方数 j²（j 从 1 到 ⌊√i⌋），那么：

$$dp[i] = 1 + \min_{1 \le j \le \lfloor\sqrt{i}\rfloor} dp[i - j^2]$$

即：先凑出 i - j²，再用一个 j² 补上。

边界条件：dp[0] = 0（凑出 0 不需要任何数）。

遍历顺序：dp[i] 只依赖比 i 更小的状态，所以 i 从小到大遍历即可。

直觉理解：把 i 拆成「一个完全平方数 + 剩余部分」，剩余的再递归求解。因为每个平方数可以重复使用，所以这本质是完全背包。

代码

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[n]

复杂度分析

• 时间复杂度：$O(n\sqrt{n})$，共 n 个状态，每个状态枚举 $O(\sqrt{n})$ 个平方数。
• 空间复杂度：$O(n)$，dp 数组长度为 n + 1。

---

方法二：完全背包（写法更通用）

思路及解法

把问题看作完全背包：

• 物品：所有不超过 n 的完全平方数 1, 4, 9, ...；
• 容量：n；
• 目标：装满容量 n 的最小物品数（每个物品可重复取）。

dp[j] 表示「凑出容量 j 的最少物品数」，初始化 dp[0] = 0，其余为 inf。

外层枚举物品 i，内层正序枚举容量 j（完全背包的标准写法）。

代码

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        # 枚举物品：所有 ≤ n 的完全平方数
        i = 1
        while i * i <= n:
            square = i * i
            # 完全背包：内层正序遍历容量
            for j in range(square, n + 1):
                dp[j] = min(dp[j], dp[j - square] + 1)
            i += 1

        return dp[n]

复杂度分析

• 时间复杂度：$O(n\sqrt{n})$，外层 $\sqrt{n}$ 个物品，内层 $O(n)$ 容量。
• 空间复杂度：$O(n)$。

和方法一是同一个复杂度，只是视角不同（一个是「按 i 拆解」，一个是「按物品枚举」）。

---

方法三：四平方和定理（数学，$O(\sqrt{n})$）

思路及解法

拉格朗日四平方和定理：任何正整数都可以表示为至多 4 个正整数的平方和。

更强的结论（勒让德三平方定理）：当且仅当 n = 4^k × (8m + 7) 时，n 不能被表示为 3 个平方数之和，也就是恰好需要 4 个。

据此，答案只可能是 1、2、3、4 中的一个，分类讨论：

1. 答案为 1：n 本身就是完全平方数；
2. 答案为 4：n 满足 4^k × (8m + 7) 的形式；
3. 答案为 2：存在 a 使得 n - a² 是完全平方数；
4. 答案为 3：以上都不是。

判断 4^k × (8m + 7) 的方法：不断除以 4，直到不能整除，然后看余数是否 % 8 == 7。

代码

from math import isqrt

class Solution:
    def numSquares(self, n: int) -> int:
        def is_perfect_square(x: int) -> bool:
            s = isqrt(x)
            return s * s == x

        def check_answer4(x: int) -> bool:
            # 判断 x 是否是 4^k * (8m + 7) 的形式
            while x % 4 == 0:
                x //= 4
            return x % 8 == 7

        if is_perfect_square(n):
            return 1
        if check_answer4(n):
            return 4

        # 判断答案是否为 2
        i = 1
        while i * i <= n:
            if is_perfect_square(n - i * i):
                return 2
            i += 1

        return 3

复杂度分析

• 时间复杂度：$O(\sqrt{n})$，主要开销在「判断答案是否为 2」的枚举上。
• 空间复杂度：$O(1)$，只使用常数个变量。

---

三种方法对比

方法	时间	空间	特点
DP（按 i 拆解）	$O(n\sqrt{n})$	$O(n)$	思路直观，容易讲
完全背包	$O(n\sqrt{n})$	$O(n)$	通用模板，可迁移到其他背包问题
数学（四平方和定理）	$O(\sqrt{n})$	$O(1)$	最优，但需要数学知识

推荐：

• 面试：首选 DP，思路清晰、代码短、容易讲；
• 加分：可以补充数学解法，展示对四平方和定理的理解；
• 实际使用：数学解法最快，但面试官未必喜欢纯数学的「黑科技」。

---

关键细节

1. dp[0] = 0 的意义

凑出 0 不需要任何完全平方数。它让转移方程在「i 本身就是一个完全平方数」时也能统一处理：dp[i] = dp[0] + 1 = 1。

2. DP 方法的枚举范围

枚举 j² 时，j 的范围是 1 到 ⌊√i⌋。因为 j² ≤ i 才能使用（不能超过目标值）。

3. 完全背包与 0-1 背包的区别

	0-1 背包	完全背包
每个物品	最多取一次	可取无限次
内层容量遍历方向	倒序	正序

本题每个完全平方数可以重复使用，所以是完全背包。

4. 四平方和定理的关键结论

• 答案 ≤ 4；
• 答案为 4 ⟺ n = 4^k × (8m + 7)；
• 答案为 1 ⟺ n 是完全平方数；
• 答案为 2 ⟺ n - a² 是完全平方数（a 从 1 枚举）。

4^k × (8m + 7) 形式的判断可以简化为「不断除以 4，直到不能整除，看是否 % 8 == 7」。

5. 为什么不用 BFS

本题也可以用 BFS：从 n 出发，每次减去一个完全平方数，求到 0 的最短路径。思路直观但效率一般。DP 是更常见的解法。

---

总结

• 本质：用最少的完全平方数凑出 n，等价于完全背包；
• DP 转移：dp[i] = 1 + min(dp[i - j²])，j² ≤ i；
• 边界：dp[0] = 0；
• 答案范围：只需 1、2、3、4 四种可能（四平方和定理）；
• 分类讨论：
  • 完全平方数 → 1；
  • 4^k × (8m + 7) 形式 → 4；
  • n - a² 是完全平方数 → 2；
  • 其余 → 3；
• 通用套路：「凑出目标的最少数量」+ 「元素可重复使用」→ 完全背包。

相关题目

• LC 322. 零钱兑换（完全背包）
• LC 377. 组合总和 IV（完全背包，求方案数）
• LC 416. 分割等和子集（0-1 背包）
• LC 204. 计数质数（数学 + 筛法）