好的，我们来看 LeetCode 第 279 题：完全平方数（Perfect Squares）。

1. 题目描述

给你一个正整数 n，你的任务是：找到若干个完全平方数（比如 1, 4, 9, 16, …），使它们的和等于 n，并且要求完全平方数的个数最少。
返回最少需要的完全平方数的个数。

示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4（最少 3 个平方数，而不是 12 = 9 + 1 + 1 + 1 的 4 个）。

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

2. 思路分析

2.1 问题转化

这个问题可以看作：

• 数字 n 是我们要凑成的目标总额。
• 可用的硬币面额是：1, 4, 9, 16, … ( ≤ n 的平方数)。
• 我们要用最少的硬币数凑成总额 n。

这是一个典型的完全背包问题（物品可以无限使用，但这里物品是平方数，每种平方数用一次以上可能重复）。

2.2 动态规划定义

定义 dp[i] 表示：凑成整数 i 所需的最少完全平方数的个数。

初始状态：

• dp[0] = 0（凑成 0 需要 0 个平方数）
• 对于 i ≥ 1，先设 dp[i] 为一个很大的数（比如 i 本身，因为最坏情况是全部用 1 来凑，需要 i 个）。

2.3 状态转移

对于每个 i，我们尝试所有可能的平方数 j*j（其中 j*j ≤ i），看是否可以用 j*j 作为最后一个平方数：
如果这样，那么 i 的个数 = i - j*j 的个数 + 1。

公式：

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

其中 j 从 1 到 j*j ≤ i。

2.4 例子演算（n = 12）

初始化：dp[0]=0，其他初始化为 i（即 dp[1]=1, dp[2]=2, ... 先假设全用 1 凑）。

i=1：平方数 ≤1 的是 1
dp[1] = min(dp[1], dp[0]+1) = min(1, 0+1) = 1

i=2：平方数 ≤2 的是 1
dp[2] = min(dp[2], dp[1]+1) = min(2, 1+1) = 2

i=3：平方数 ≤3 的是 1
dp[3] = min(3, dp[2]+1) = min(3, 3) = 3

i=4：平方数 ≤4 的有 1, 4

• 用 1：dp[4] = min(4, dp[3]+1) = min(4, 4) = 4
• 用 4：dp[4] = min(4, dp[0]+1) = min(4, 1) = 1
  所以 dp[4] = 1

i=5：平方数 ≤5 的有 1, 4

• 用 1：dp[5] = min(5, dp[4]+1) = min(5, 2) = 2
• 用 4：dp[5] = min(2, dp[1]+1) = min(2, 2) = 2
  所以 dp[5] = 2

继续到 i=12：
检查平方数 1, 4, 9（因为 16>12）：

• 用 1：dp[12] = min(12, dp[11]+1) 先不忙，看别的
• 用 4：dp[12] = min(当前值, dp[8]+1)，而 dp[8] 之前算出是 2（8=4+4），所以 2+1=3
• 用 9：dp[12] = min(3, dp[3]+1) = min(3, 3+1=4) = 3
  最终 dp[12] = 3。

3. 数学优化（四平方和定理）

实际上这个问题有数学定理（Lagrange 四平方和定理）：
任何正整数都可以表示为 4 个整数的平方和（某些数可以更少）。
并且有结论：

• 如果 n 是完全平方数 → 答案是 1
• 如果 n 可以写成 4^a(8b+7) 形式 → 答案是 4
• 如果 n 减去一个平方数后剩下的是平方数 → 答案是 2
• 否则答案是 3

这样可以在 O(√n) 或 O(1) 时间内解决，但这里我们先掌握通用 DP 解法。

4. 代码实现（DP 完全背包）

def numSquares(n: int) -> int:
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    
    # 遍历每个数字 i
    for i in range(1, n + 1):
        # 尝试所有平方数 j*j
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j*j] + 1)
            j += 1
    
    return dp[n]

5. 复杂度分析

• 时间复杂度：O(n √n)
  外层循环 O(n)，内层循环 O(√n)（因为 j 最大到 √n）。
• 空间复杂度：O(n)（dp 数组）。

6. 总结

这道题是完全背包问题的变种，硬币面额是平方数。
通过 DP 可以较直观地解决，同时了解背后的数学定理可以进一步优化到更快。
关键在于定义 dp[i] 为凑成 i 所需的最少平方数个数，利用 dp[i] = min(dp[i], dp[i - sq] + 1) 进行递推。