⼩杨和整数拆分

题目描述

⼩杨有⼀个正整数 ，⼩杨想将它拆分成若⼲完全平⽅数的和，同时⼩杨希望拆分的数量越少越好。 ⼩杨请你编写程序计算出总和为 的完全平⽅数的最少数量。

输入格式

第⼀⾏包含⼀个正整数 ，含义如题⾯所⽰。

输出格式

输出⼀个整数，代表总和为 的完全平⽅数的最少数量。 3.1.4 样例1 1 18 1 2 ，其中最少需要 个完全平⽅数。 子任务编号 数据点占比 1 20% 2 40% 3 40% 对于全部数据，保证有 。 3.1.5 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 int n; 5 int dp[N]; 6 int main(){ 7 cin>>n; 8 for(int i=1;i<=n;i++){ 9 dp[i]=i; 10 for(int j=1;j<=sqrt(i);j++){ 11 dp[i] =min(dp[i-j*j]+1,dp[i]); 12 } 13 } 14 cout<<dp[n]<<"\n"; 15 }

样例输入 #1

1 18
1 2
，其中最少需要 个完全平⽅数。
子任务编号 数据点占比
1 20%
2 40%
3 40%

样例输出 #1

数据范围

见题目描述

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。