GESP 题解库 / 6 级题解 / [GESP202409 六级] 小杨和整数拆分 · 第 14 / 27 题
GESP202409 六级 · P11246 · 简单

小杨和整数拆分

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

📊
n ≤ 10⁵
数值范围
🔢
int
数值类型
⚡
O(n√n)
时间复杂度
🎯
完全背包 / 四平方和定理
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定正整数 n,把它拆成若干个完全平方数之和(允许重复),求所需平方数的最少数量。

例:18 = 9 + 9 = 3² + 3²,所以答案是 2。

💡
人话翻译:本质上是一道完全背包——"物品"是所有不超过 n 的平方数 1, 4, 9, 16, …,每个物品可以重复使用,要"凑出恰好 n"且用最少的件数。
定义 dp[i] = 凑出 i 所需的最少平方数个数,则 dp[i] = 1 + min(dp[i − s])(s 为不超过 i 的平方数)。
另外还有一个漂亮的数学结论:答案只可能是 1、2、3、4。

🔍 关键词提取

完全背包完全平方数四平方和定理最小值 DP

已知条件

项目说明
输入一个正整数 n
输出最少需要的完全平方数个数
数据范围1 ≤ n ≤ 10⁵
约束拆出的数必须是完全平方数,可重复
目标数量最少

需要解决的问题

02
思维导图
整理解题思路的全貌
🔢 dp[i] = 1 + min(dp[i − s])
🧠 状态定义
dp[i]:凑出 i 的最少个数
dp[0] = 0
答案是 dp[n]
按 i 递增递推
🔁 转移
枚举最后一个平方数 s
s 取 1、4、9、16…(≤ i)
dp[i] = min(dp[i−s] + 1)
平方数可重复使用
📐 数学视角
四平方和定理:答案 ≤ 4
是完全平方数 → 1
能拆成 a²+b² → 2
形如 4ᵏ(8m+7) → 4,否则 3
⚠️ 易错点
dp 初值设太大(应用 n 或 INF)
枚举平方数时越界
把"可重复"当成"只能用一次"
循环方向写错
03
样例手算推导
样例与几个小例子的验证

🧮 样例:n = 18,答案 2

先看能不能用 1 个:18 不是完全平方数(4²=16、5²=25)✗。再看 2 个:

拆分方式是否都是平方数结论
1 + 1717 不是 ✗—
4 + 1414 不是 ✗—
9 + 99 = 3² ✓✓✅ 可以!
16 + 22 不是 ✗—

18 = 3² + 3² → 答案 2 ✓

用 DP 也算一遍(枚举不超过 18 的平方数:1、4、9、16):

i可用拆分dp[i]
0—0
111
21 + 12
31 + 1 + 13
44(=2²)1
54 + 12
84 + 42
99(=3²)1
124 + 4 + 43
1616(=4²)1
1716 + 12
189 + 92
🔑
注意 12 = 4+4+4 需要 3 个,而 16 只要 1 个。这说明"数值越大不一定越难拆"——关键看它离最近的平方数有多远。
DP 的正确性在于:它把"最后一个平方数是谁"的所有可能性都试了一遍,取最小值就一定最优。

🧮 数学方法的验证(4 个已知上界)

拉格朗日四平方和定理告诉我们答案只会是 1、2、3、4。下面用几个例子感受一下判定方法。

n判定过程答案
99 = 3²,是完全平方数1
18非平方数;18 = 9 + 9 ✓2
12非平方数;12 − 1 = 11 ✗、12 − 4 = 8 ✗、12 − 9 = 3 ✗(都不平方);12 = 4 × 3,3 % 8 = 3 ≠ 7 → 33
77 不是平方数;7−1=6 ✗、7−4=3 ✗;7 % 8 = 7 → 44
2828 = 4 × 7,7 % 8 = 7 → 44
100000是平方数?√100000 ≈ 316.2 ✗;100000 = 316² + 144 = 99856 + 144 ✓ → 22
1
判定 3 与 4 的依据

勒让德三平方和定理:

n 能写成三个平方数之和 ⟺ n 不形如 4ᵃ(8b + 7)

所以:先把 n 中的因子 4 全部除掉

若剩下部分 % 8 == 7 → 答案是 4

否则答案是 3(在已排除 1、2 的前提下)

O(√n) 判定

⚠️
如果没把握记住定理,用 DP 更稳妥:DP 一定能算出正确答案,而数学方法需要记住"勒让德三平方和定理"的细节,写错一个余数条件就会全错。
所以:DP 是通用解法,定理是"锦上添花"。
04
解法对比
DP vs 四平方和定理

⚔️ 解法对比

🟢 完全背包式 DP(推荐) 推荐

dp[i] = 1 + min(dp[i − s]),s 遍历不超过 i 的平方数

  • 时间 O(n√n) ≈ 3 × 10⁷
  • n = 10⁵ 时约 3000 万次
  • 代码 15 行
  • 不需要任何数论知识
💡
实现细节:先预处理出所有 ≤ n 的平方数;外层 i 从 1 到 n,内层枚举平方数 s ≤ i,dp[i] = min(dp[i], dp[i−s] + 1)。注意平方数可以重复使用,所以这就是完全背包、不需要额外限制。

🟠 四平方和定理 O(√n)

用"答案 ∈ {1,2,3,4}"加判定条件直接得答案

  • 时间 O(√n) ≈ 316
  • 极快,代码 20 行
  • 但需要掌握勒让德三平方和定理
  • 条件写错就全错
⚠️
适合什么场景:如果 n 达到 10¹⁸ 级别,DP 完全不可行,就只能用定理。本题 n ≤ 10⁵,DP 已经足够。

📈 性能对比

方案复杂度(n = 10⁵)依赖
完全背包 DP约 3 × 10⁷无(通用)
四平方和定理约 316需要数论知识
05
算法流程图
完全背包式 DP 求最少平方数
开始读入 n;dp[0] = 0,dp[1..n] 初始化为一个大值i 从 1 到 ns 从 1 开始,只要 s × s ≤ i 就继续dp[i] = min(dp[i], dp[i − s×s] + 1)i 是否已经到 n?输出 dp[n]i 加 1 递推下一个数
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔢 最少平方数个数

输入一个正整数 n,程序会算出最少需要几个完全平方数,并给出一种拆法。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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 里一个很实用的小技巧:初值取"已知的可行上界"而不是"无穷大"。

📖 关键几行怎么看

代码作用为什么这样写
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。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
182题面样例:9 + 9
111 = 1²
414 = 2²
1234 + 4 + 4
74需要 4 个:4 + 1 + 1 + 1
100000运行验证最大规模,注意效率
✅
自查清单:① 初值安全吗?② 平方数枚举范围对吗?③ dp[0] = 0 吗?

🚨 易错点清单

⚠️
初值溢出:用 INT_MAX 时 +1 会溢出,改用 n 作上界更安全。
⚠️
平方数枚举越界:条件是 s * s <= i。
⚠️
误解约束:平方数可以重复使用(12 = 4 + 4 + 4)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n√n)
空间复杂度
O(n)
运算量(n = 10⁵)
约 3 × 10⁷
数学解法
O(√n)

时间怎么算的?

空间都用在哪?

一个长度 n + 1 的 dp 数组。

✅ 约 3000 万次运算,C++ 约 0.1 秒,可通过。若 n 更大(如 10¹⁸),就要用四平方和定理的 O(√n) 做法。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 完全背包式 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 时的数论加速
🌟
思考题:如果题目改成"拆成若干个任意正整数之和,使它们的乘积最大",这题怎么做?(提示:完全不同了——那是最经典的"剪绳子"问题,答案是"尽量拆成 3"(余 1 时改成 2+2)。可见"约束"和"目标"一变,方法就从背包/数论变成了贪心。)