class Solution {
public:
int numSquares(int n) {
// int ret=INT_MAX;
if(n==0)return 0;
return numSquares( n,1,INT_MAX);
}
int numSquares(int n,int deep,int min) {
if(deep>=min)return min;
int sq=sqrt(n);
if(sq*sq==n) { return 1;}
for(int i=sq;i>=1;i)
{
int temp=1+numSquares(ni*i,deep+1,min);
if( temp<min)min=temp;
}
return min;
}
};
My simple dfs method C++


hard to explan.. what's the meaning of min in the function?
it seems that it has mix meaning of min of curent min and total min,
so I change it by seprate them by add current mi:int numSquares(int n,int deep,int min) { if(deep>=min)return min; int sq=sqrt(n); if(sq*sq==n) { return 1;} int mi = mindeep+1; for(int i=sq;i>=1;i) { int temp=1+numSquares(ni*i,deep+1,min); if( temp<mi) { mi=temp; min = deep + mi 1; } } return mi;

My method is very similar to yours, but instead of search previous numSquares using "n  i * i", I try to jump as far as possible using "n % i * i". My method takes only 16ms.
int numSquares(int n) { int squares = n; numSquares(n, 0, squares); return squares; } // Top down DP void numSquares(int n, int cnt, int& squares) { if (cnt >= squares) return; if (n == 0) { squares = min(squares, cnt); return; } for (int i = sqrt(n); i >= 1; i) { numSquares(n % (i * i), cnt + n / (i * i), squares); } }