优化暴搜也能过？时间复杂度超了吧。

数据水了吧，强烈要求加强数据。

未优化代码（40）

#include<iostream>
#include<cmath>
using namespace std;
int n,a[355],k,d=1e8;
void dfs(int x,int step,int k){
	if(x==0){
		d=min(d,step);
		return ;
	}
	for(int i=k;i>=1;i--){
		if(x>=a[i]){
			dfs(x-a[i],step+1,i);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=350;i++){
		if(i*i>100000){
			k=i-1;
			break;
		}
		a[i]=i*i;
	}
	dfs(n,0,k);
	cout<<d;
	return 0;
} 

剪枝dfs（100）

void dfs(int x,int step,int k){
	if(x==0){
		d=min(d,step);
		return ;
	}
	if(step>=d) return ;
	for(int i=k;i>=1;i--){
		if(x>=a[i]){
			dfs(x-a[i],step+1,i);
		}
	}
}

n=350的暴搜优化一下也能过？有没有大佬来为本蒟蒻解释一下，是数据水了还是本身就能过？