4648: 【GESP2409六级】小杨和整数拆分
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
正整数$n$ ，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。
小杨请你编写程序计算出总和为$n$ 的完全平方数的最少数量。
小杨请你编写程序计算出总和为$n$ 的完全平方数的最少数量。
输入
第一行包含一个正整数$n$ ，含义如题面所示。
输出
输出一个整数，代表总和为$n$ 的完全平方数的最少数量。
样例输入 复制
18样例输出 复制
2提示
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int dp[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
dp[i]=i;
for(int j=1;j<=sqrt(i);j++){
dp[i] =min(dp[i-j*j]+1,dp[i]);
}
}
cout<<dp[n]<<"\n";
}