279. 完全平方数

题目链接：279. 完全平方数

题目描述

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

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

核心思考：完全背包思想（DFS + 记忆化）

本题可以抽象为一个完全背包问题：给出一系列面额为完全平方数（1, 4, 9, ...）的硬币，求凑出金额 n 所需的最少硬币个数。

1. 状态定义：设 dfs(i, j) 为：使用前 i 个完全平方数（即 $1^2, 2^2, \dots, i^2$）来凑出目标和 j 时所需要的最小完全平方数数量。
2. 决策转移：
   • 不选第 i 个平方数：直接从前 i-1 个中凑出 j：dfs(i - 1, j)。
   • 选第 i 个平方数：目标变小，由于可以重复选，索引 i 不变：dfs(i, j - i*i) + 1。
   • 二者取最小值：min(dfs(i - 1, j), dfs(i, j - i*i) + 1)。
3. 递归边界：
   • 如果 $j < i^2$：当前平方数太大，只能选择不选，向下退至 dfs(i - 1, j)。
   • 如果 $i == 0$：即没有可选的数字了。如果此时 $j == 0$，返回 0；如果 $j > 0$，说明无法凑出，返回无穷大 inf。
4. 性能保障：由于同一 (i, j) 状态会被多次访问，使用 Python 的 @cache 装饰器进行记忆化，将重复计算的时间复杂度从指数级降到多项式级。

解题思路 (Python)

class Solution:
    def numSquares(self, n: int) -> int:
        # 起始状态：从可以用到最大的完全平方数开始，凑出 n
        return dfs(isqrt(n), n)

# 递归状态定义：用前 i 个完全平方数合成 j 的最小数量
@cache
def dfs(i, j):
    # 边界情况：没有可选数字了
    if i == 0:
        return 0 if j == 0 else inf
    
    # 如果目标值小于当前的平方数，当前数字无法被选择
    if j < i**2:
        return dfs(i - 1, j)
    
    # 完全背包决策：min(不选, 选一个后继续停在当前层)
    return min(dfs(i - 1, j), dfs(i, j - i * i) + 1)

复杂度分析

• 时间复杂度：$O(N \sqrt{N})$，其中 $N = n$。状态总数为 $N \times \sqrt{N}$，每个状态计算一次。
• 空间复杂度：$O(N \sqrt{N})$。主要用于存储缓存字典及递归栈开销。