题目描述
给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
输入输出描述
输入描述
一个整数n,表示要组成的数字
输出描述
一个正数表示最少需要几个完全平方数才能组成
输入输出样例
输入格式#1:4
输出格式#1:1
输入格式#2:10
输出格式#2:2
输入格式#3:19
输出格式#3:3
输入格式#4:245
输出格式#4:2
输入格式#5:3281
输出格式#5:2
输入格式#6:234
输出格式#6:2
输入格式#7:666
输出格式#7:2
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;//4
int k=(int)sqrt(n);
int dp[n+1];
dp[0]=0;
int pingfang[k+1];
for(int i=1;i<k+1;i++){
pingfang[i]=i*i;
}
for(int i=1;i<n+1;i++){
dp[i]=i;
}
for(int i=2;i<n+1;i++){
for(int j=2;j<k+1;j++){
if(pingfang[j]>i){
continue;
}
if(pingfang[j]<=i) {
int index=i/pingfang[j];
dp[i]=min(dp[i], dp[i-index*pingfang[j]]+index);
}
}
}
cout<<dp[n];
return 0;
}