把 n 拆成若干完全平方数之和,求最少个数。
给定正整数 n,把它拆成若干个完全平方数之和(允许重复),求所需平方数的最少数量。
例:18 = 9 + 9 = 3² + 3²,所以答案是 2。
1, 4, 9, 16, …,每个物品可以重复使用,要"凑出恰好 n"且用最少的件数。dp[i] = 凑出 i 所需的最少平方数个数,则 dp[i] = 1 + min(dp[i − s])(s 为不超过 i 的平方数)。完全背包完全平方数四平方和定理最小值 DP
| 项目 | 说明 |
|---|---|
| 输入 | 一个正整数 n |
| 输出 | 最少需要的完全平方数个数 |
| 数据范围 | 1 ≤ n ≤ 10⁵ |
| 约束 | 拆出的数必须是完全平方数,可重复 |
| 目标 | 数量最少 |
dp[i] = 凑出 i 的最少个数,dp[0] = 0dp[i] = min(dp[i − s] + 1)先看能不能用 1 个:18 不是完全平方数(4²=16、5²=25)✗。再看 2 个:
| 拆分方式 | 是否都是平方数 | 结论 |
|---|---|---|
| 1 + 17 | 17 不是 ✗ | — |
| 4 + 14 | 14 不是 ✗ | — |
| 9 + 9 | 9 = 3² ✓✓ | ✅ 可以! |
| 16 + 2 | 2 不是 ✗ | — |
18 = 3² + 3² → 答案 2 ✓
用 DP 也算一遍(枚举不超过 18 的平方数:1、4、9、16):
| i | 可用拆分 | dp[i] |
|---|---|---|
| 0 | — | 0 |
| 1 | 1 | 1 |
| 2 | 1 + 1 | 2 |
| 3 | 1 + 1 + 1 | 3 |
| 4 | 4(=2²) | 1 |
| 5 | 4 + 1 | 2 |
| 8 | 4 + 4 | 2 |
| 9 | 9(=3²) | 1 |
| 12 | 4 + 4 + 4 | 3 |
| 16 | 16(=4²) | 1 |
| 17 | 16 + 1 | 2 |
| 18 | 9 + 9 | 2 |
拉格朗日四平方和定理告诉我们答案只会是 1、2、3、4。下面用几个例子感受一下判定方法。
| n | 判定过程 | 答案 |
|---|---|---|
| 9 | 9 = 3²,是完全平方数 | 1 |
| 18 | 非平方数;18 = 9 + 9 ✓ | 2 |
| 12 | 非平方数;12 − 1 = 11 ✗、12 − 4 = 8 ✗、12 − 9 = 3 ✗(都不平方);12 = 4 × 3,3 % 8 = 3 ≠ 7 → 3 | 3 |
| 7 | 7 不是平方数;7−1=6 ✗、7−4=3 ✗;7 % 8 = 7 → 4 | 4 |
| 28 | 28 = 4 × 7,7 % 8 = 7 → 4 | 4 |
| 100000 | 是平方数?√100000 ≈ 316.2 ✗;100000 = 316² + 144 = 99856 + 144 ✓ → 2 | 2 |
勒让德三平方和定理:
n 能写成三个平方数之和 ⟺ n 不形如 4ᵃ(8b + 7)
所以:先把 n 中的因子 4 全部除掉
若剩下部分 % 8 == 7 → 答案是 4
否则答案是 3(在已排除 1、2 的前提下)
O(√n) 判定
dp[i] = 1 + min(dp[i − s]),s 遍历不超过 i 的平方数
dp[i] = min(dp[i], dp[i−s] + 1)。注意平方数可以重复使用,所以这就是完全背包、不需要额外限制。用"答案 ∈ {1,2,3,4}"加判定条件直接得答案
| 方案 | 复杂度(n = 10⁵) | 依赖 |
|---|---|---|
| 完全背包 DP | 约 3 × 10⁷ | 无(通用) |
| 四平方和定理 | 约 316 | 需要数论知识 |
输入一个正整数 n,程序会算出最少需要几个完全平方数,并给出一种拆法。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int dp[100005]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) dp[i] = n; // 初值取一个足够大的数 dp[0] = 0; for (int i = 1; i <= n; i++) { for (int s = 1; s * s <= i; s++) { dp[i] = min(dp[i], dp[i - s * s] + 1); } } printf("%d\n", dp[n]); return 0; }
n 就够大?因为最坏情况是把 n 拆成 n 个 1(1 = 1²),所以答案一定 ≤ n。把初值设成 n 既能保证"一定被更新",又不会因为相加而溢出(如果用 INT_MAX,dp[i - s*s] + 1 就可能整数溢出)。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
dp[i] = n | 初值 | 最坏是 n 个 1,所以 n 是合法上界 |
dp[0] = 0 | 边界 | 凑出 0 不需要任何数 |
s * s <= i | 枚举范围 | 平方数不能超过 i |
dp[i - s*s] + 1 | 转移 | 用掉一个平方数 s²,件数加一 |
INT_MAX 导致 +1 溢出;② 枚举平方数时写成 s <= i(越界且低效);③ 把"可重复使用"当成"每个平方数只能用一次";④ 忘了 dp[0] = 0。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
18 | 2 | 题面样例:9 + 9 |
1 | 1 | 1 = 1² |
4 | 1 | 4 = 2² |
12 | 3 | 4 + 4 + 4 |
7 | 4 | 需要 4 个:4 + 1 + 1 + 1 |
100000 | 运行验证 | 最大规模,注意效率 |
INT_MAX 时 +1 会溢出,改用 n 作上界更安全。s * s <= i。一个长度 n + 1 的 dp 数组。
✅ 约 3000 万次运算,C++ 约 0.1 秒,可通过。若 n 更大(如 10¹⁸),就要用四平方和定理的 O(√n) 做法。
// 完全背包式 DP 骨架 dp[0] = 0; for (int i = 1; i <= n; i++) { dp[i] = 上界; // 取一个安全的初值 for (int s = 1; s * s <= i; s++) dp[i] = min(dp[i], dp[i - s * s] + 1); } // 四平方和判定(O(sqrt(n)) 版本) // 答案只可能是 1、2、3、4 int solveFast(int n) { // 1. 是完全平方数 -> 1 int r = (int)(sqrt((double)n) + 0.5); if (r * r == n) return 1; // 2. 能拆成两个平方数之和 -> 2 for (int a = 1; a * a * 2 <= n; a++) { int t = n - a * a; int b = (int)(sqrt((double)t) + 0.5); if (b * b == t) return 2; } // 3/4. 利用勒让德三平方和定理 while (n % 4 == 0) n /= 4; if (n % 8 == 7) return 4; return 3; } // 一些相关结论 // - 拉格朗日四平方和定理:任何正整数 = 至多 4 个平方数之和 // - 勒让德三平方和定理:n 需要 4 个 当且仅当 n = 4^a(8b+7)
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 完全背包 | 物品可重复使用 | 凑数、找零、最少件数问题 |
| 安全初值 | 取已知上界而非 INT_MAX | 所有最小值 DP |
| 四平方和定理 | 答案 ∈ {1,2,3,4} | 大 n 时的数论加速 |