力扣 完全平方数

一、题目回顾

给定一个正整数n，要求找到最少数量的完全平方数（如 1, 4, 9, 16, …），使它们的和等于n。

示例

• n = 12 → 4 + 4 + 4 → 3

• n = 13 → 4 + 9 → 2

本质问题一句话总结：

把 n 拆成若干个完全平方数之和，要求个数最少

二、第一反应：这是一个“最少”问题

一看到「最少多少个」，而且允许重复使用数字，很容易联想到：

• 背包问题

• 动态规划

• 状态转移

而这里的“物品”就是所有 ≤ n 的完全平方数。

三、状态设计（这是题目的核心）

1️⃣ 状态定义

设：

dp[i]表示组成数字 i 所需要的最少完全平方数个数

目标就是求dp[n]

2️⃣ 状态初始化

• dp[0] = 0
  组成 0 不需要任何数（很重要的边界）

• 其他dp[i]初始可以设成一个很大的值（表示“还没算出来”）

四、关键一步：状态转移怎么来？

思考方式（非常重要）

假设我们要算dp[i]：

• 如果最后一步用了一个平方数k²

• 那么在此之前，已经凑出了i - k²

• 所以：

dp[i] = dp[i - k^2] + 1

但问题是：

k 可以取多少？

只枚举到 √i（平方根技巧）

因为：

• k² ≤ i

• 所以 k ≤ √i

这一步非常关键，它直接决定了复杂度。

于是有：

dp[i] = min (dp[i - k^2] + 1)

class Solution { public: int numSquares(int n) { int dp[10001]; for (int i=1;i<=n;i++) { int num=(int)std::sqrt(i); int min=100000; for(int j=1;j<=num;j++) { if (dp[i-j*j]+1<min) min=dp[i-j*j]+1; } dp[i]=min; } return dp[n]; } };

五、算法流程总结（口语版）

1. 从 1 一路算到 n

2. 对于每个 i：

   • 枚举所有k² ≤ i

   • 尝试用k²作为最后一个数

   • 更新最小值

3. 最终返回dp[n]