# Dp solution like question 322 coin change

• ``````class Solution {
public:
int numSquares(int n) {
vector<int> num(n + 1, 0);
int size = (int)sqrt(n);
num[0] = 0;
for(int i = 1; i <= n; i++)
{
int lmin = INT_MAX;
for(int j = 1; j <= size; j++)
{
if(i - j * j >= 0 && num[i - j * j] < lmin)
lmin = num[i - j * j];
}
num[i] = lmin + 1;
}
return num[n];
}
};``````

• Brute Force DFS solution in C ,Only 4ms!!!!!

`````` #define MAXN (0xffff + 1)
#define INF (0x3fffffff)
#define MAX_CNT (0xffffff)

unsigned int square[MAXN]={0};
int ans[MAX_CNT]={0};

int count(int rest,int power)
{
if(rest < 4 || power < 2)
return ans[rest]=rest;
if(rest < MAX_CNT && ans[rest])
return ans[rest];
int ret = 20;
for(int i= power; i > 0 ; i--)
{
int rst = rest % square[i];
int tmp = rest / square[i];
if(tmp >= ret)
break;
tmp += count(rst,sqrt(rst));
if( tmp < ret)
ret = tmp;
}
return ans[rest]=ret;
}

int numSquares(int n) {
if(!square[1])
{
unsigned int idx = 1;
for( ; idx < MAXN; idx ++)
square[idx] = idx * idx;
}
return count(n,sqrt(n));
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.