题目描述

给定正整数 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;
}