力扣 完全平方数
一、题目回顾
给定一个正整数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 一路算到 n
对于每个 i：
枚举所有
k² ≤ i尝试用
k²作为最后一个数更新最小值
最终返回
dp[n]