谁来分析一下

暴力17ms

dp169ms

#include <iostream>//暴力代码
using namespace std;
int dp[320],h,d,c,hdc=100000,num[320];
int inti(){
    int i;
    for(i=1;i*i<=h;i++) num[i]=i*i;
    return i;
}
int main(){
	scanf("%d",&h);
	d=inti(),c=d-1;
	for(int i=1;i<=c;i++){
		int cnt=0;
		for(int j=--d;j>0;j--){
			while(num[j]+dp[i]<=h){
				dp[i]+=num[j],cnt++;
				if(cnt>=hdc) break;
			}
			if(cnt>=hdc) break;
		}
		hdc=min(cnt,hdc);
	}
	printf("%d",hdc);
    return 0;
}

#include <iostream>//dp代码
using namespace std;
const int N=1e5+10;
int n,dp[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        dp[i]=i;
        for(int j=1;j<=i/j;j++){
            dp[i]=min(dp[i-j*j]+1,dp[i]);
        }
    }
    printf("%d",dp[n]);
    return 0;
}