时间超限，能没有其他方法或者优化一下？

#include<bits/stdc++.h>
using namespace std;
void dfs(int now,int n);
int a,ans=1000000;
int next_[18]={0,1,16,81,256,625,1296,2401,4096,6561,10000,14641,20736,28561,38416,50625,65536,83521};
int main()
{
	
	scanf("%d",&a);
	dfs(0,0);
	cout<<ans;
	return 0;
}
inline void dfs(int now,int n)
{
	
	if(now==a)
	{
		ans=min(n,ans);
		return;
	}
	for(int i = 17;i>=1;i--)
	{
		int t=now+next_[i];
		if(now<=a)
		{
			dfs(t,n+1);
		}		
	}
}