3989：[GESP202409六级] 小杨和整数拆分

## 题目背景 2024 年 9 月 GESP C++ 六级编程第 1 题 ## 题目描述 ⼩杨有⼀个正整数 $n$，⼩杨想将它拆分成若⼲完全平⽅数的和，同时⼩杨希望拆分的数量越少越好。 ⼩杨请你编写程序计算出总和为 $n$ 的完全平⽅数的最少数量。 ## 输入格式 第⼀⾏包含⼀个正整数 $n$，含义如题⾯所⽰。 ## 输出格式 输出⼀个整数，代表总和为 $n$ 的完全平⽅数的最少数量。 ## 样例1 ```input1 18 ``` ```output1 2 ``` ## 样例解释 $18=9+9=16+1+1$ ，其中最少需要 $2$ 个完全平⽅数。 ## 数据范围 | 子任务编号 | 数据点占比 | $n $ | | ---------- | ---------- | ----------- | | 1 | $20\%$ | $\leq 20$ | | 2 | $40\%$ | $\leq 1000$ | | 3 | $40 \%$ | $\leq 10^5$ | 对于全部数据，保证有 $1 \leq n \leq 10^5$ 。