Hi all. I'm using a Dynamic Programming to approach this problem. So the logic is:

We gonna iterate every possible number that n will start to subtract. For example 12, its sqrt is 3, so we gonna check what if 12 minus 3^2 first, what if minus 2^2 first and so on.

For every possible starting number. solution(n) = min (1 + solution(ni^2), currentResult);
So I have the following code:
int numSquaresDP(int n, map<int, int> & memo) {
if (memo.find(n) != memo.end()) {
return memo[n];
}
else {
int sqrtN = sqrt(n);
int result = INT_MAX;
for (int i = sqrtN; i > 0; i) {
int tempResult;
memo[i*i] = 1;
if (memo.find(ni*i) != memo.end()) {
tempResult = memo[ni*i];
}
else {
tempResult = numSquaresDP(ni*i, memo);
memo[ni*i] = tempResult;
}
result = min(tempResult+1, result);
}
memo[n] = result;
return result;
}
}
int numSquares(int n) {
map<int, int> memo;
memo[0] = 0;
return numSquaresDP(n,memo);
}
It compute the correct number but exceed time limit when n is great. But I have no idea what I did wrong and how should I optimize it to make it become faster. I know by doing some math trick can make this run super fast but I just want to know what I did wrong in my case. Thank you guys in advance!