完全平方数
Perfect Squares
给定正整数 n，求把它表示成若干个完全平方数之和时，最少需要几项。
在力扣中练习题目描述
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n =12输出：3 解释：12 = 4 + 4 + 4
示例 2：
输入：n =13输出：2 解释：13 = 4 + 9
提示：
1 <= n <= 104
解题思路
完全背包 · 一维 DP
枚举最后一项是哪个平方数，往前接子问题
先试贪心：每次拿不超过 n 的最大平方数。n = 18 会先拿 16，剩 2 只能用 1+1，得到 3 项；但 18 = 9+9 只要 2 项。贪心错在“当前最大”不等于“全局最少”。
把最后一项固定为某个平方数 k²，前面要凑的就是 n - k²。于是
dp[i] = min(dp[i - k²] + 1) 对所有 k² ≤ i
dp[i] 表示凑出 i 最少需要几个完全平方数
dp[14] = 34✓dp[11] = 34✓dp[6] = 34✓写入4并列最优
dp[15]=min(dp[14] + 1, dp[11] + 1, dp[6] + 1)min(3 + 1, 3 + 1, 3 + 1)=4自拟主例 n = 15，dp[15] = 4（9+4+1+1）；15 的候选来自 14、11、6，三者都是 3+1=4，并列最优。dp[0] = 0 是唯一初值；其余先记成 n + 1 当无穷。因为面额里一定有 1，任何 i 都能用 i 个 1 凑出，所以 n + 1 一定大于任何合法答案，又不会在加一时溢出。
dp[4] = min(4, 1) = 1；最优来源是 dp[0]，减去 4×4。
- i
- 4
- dp[i]
- 1
dp[i] 表示凑出 i 最少需要几个完全平方数
dp[3] = 34—dp[0] = 01✓写入1
dp[4]=min(dp[3] + 1, dp[0] + 1)min(3 + 1, 0 + 1)=1按 i 从小到大填表，每个 dp[i - k²] 都已经算好。时间 O(n√n)，空间 O(n)。最后返回 dp[n]，不需要额外判断不可达。
易错点
- 贪心地每次取最大平方数：18 会被拆成 16+1+1，而最优是 9+9。
- 用 INT_MAX 当无穷再 +1，整型溢出成负数；用 n+1 更安全。
- dp 只开到 n：dp[i-k²] 在 k²=i 时会访问 dp[0]，需要保留这个边界。
BFS · 最短步数
从 0 出发，每次加一个平方数，看几步到 n
同样是 O(n√n)，BFS 把“加一个平方数”看成一步，第一次到达 n 的层数就是答案；队列与访问数组的常数更大，但思路更接近最短路。
把每个整数看成图上的点，从 x 连到 x + k²，边权都是 1。求最少平方数，就是求 0 到 n 的最短路径长度。
BFS 按层扩展：第 1 层是 0 加一个平方数，第 2 层是再加一个……第一次遇到 n 时，层数就是最少项数。
每个点只会入队一次，时间 O(n√n)，空间 O(n)。它和 DP 是同一个状态图上的两种走法：DP 从小区间往大区间推，BFS 从 0 往外扩。
- 1把不超过 n 的平方数放进列表。
- 2dist[0] = 0，0 入队。
- 3逐层弹出，尝试 cur + sq；未访问的入队。
- 4第一次到达 n 时的 dist[n] 就是答案。
易错点
- 把平方数列表算到 n 以上：cur + sq 会越界，循环里要及时 break。
- 忘记 visited / dist 去重，同一个数反复入队，队列会膨胀。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
n = 15dp[0] = 0；其余先记为无穷，等更小的平方数给出候选。
- n
- 15
dp[i] 表示凑出 i 最少需要几个完全平方数
dp[0]=0查看 C++ 代码
延伸阅读
- 这是“完全背包求最少件数”的又一实例：物品是 1²、2²、3²……每种可用无限次。
- 判断一个数能否写成两个平方数之和、四个平方数之和，还有数论结论；本题只要求最少项数，DP 更通用。