首页 > 代码库 > 完美平方
完美平方
给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。
给出 n = 12, 返回 3 因为 12 = 4 + 4 + 4。
给出 n = 13, 返回 2 因为 13 = 4 + 9。
dp.
/* ***********************************************Author :guanjunCreated Time :2016/8/31 17:17:39File Name :1.cpp************************************************ */#include <iostream>#include <vector>#include <cmath>#include <string.h>using namespace std;int dp[1010];int n;int main(){ #ifndef ONLINE_JUDGE //freopen("in.txt","r",stdin); #endif //freopen("out.txt","w",stdout); while(cin>>n){ //dp[i]表示 组成i的最小完全平方数的个数 //那么 dp[i]=(dp[i],dp[i-j*j]+1) //初始化 全是1组成的情况 for(int i=1;i<=n;i++)dp[i]=i; for(int i=1;i<=n;i++){ for(int j=1;j*j<=i;j++){ dp[i]=min(dp[i],dp[i-j*j]+1); } } cout<<dp[n]<<endl; } return 0;}
完美平方
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。