# Why my DP method is slow?

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

1. 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.

2. For every possible starting number. solution(n) = min (1 + solution(n-i^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(n-i*i) != memo.end()) {
tempResult = memo[n-i*i];
}
else {
tempResult = numSquaresDP(n-i*i, memo);
memo[n-i*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!

• @mugua-stolaf As for DP solution, you can check my post here, but I suggest the math solution here.

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