题解 | #最少的完全平方数#
最少的完全平方数
https://www.nowcoder.com/practice/4b2f5d4c00f44a92845bdad633965c04
贪心直接解决
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n,ans;
int a[10001];
int dp[10005][10005];
int main()
{
cin>>n;
int s=sqrt(n);
for(int i=1;i<=s;i++){
a[i]=i*i;
}
while(n!=0){
for(int i=s;i>=1;i--){
while(a[i]<=n){
n-=a[i];
ans++;
}
}
}
cout<<ans;
return 0;
}
查看10道真题和解析