题目描述

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