# DP solution using static to accelerate from 324ms to 12ms in C++

• ``````class Solution {
public:
int numSquares(int n) {
static vector<int> v{0, 1};
int a = 0, b = 0, t = 0;
while(v.size() <= n)
{
a = t= v.size();
for(int i = sqrt(a); i > 0; --i)
{
b = a-i*i;
t = min(t, !b? 1 : 1+v[b]);
}
v.push_back(t);
}
return v[n];
}
};``````

• If you don't know Lagrange's four-square theorem, please check wiki first. In a summary, it's all about that the maximum will be 4 and in that case it will follow the following equation, otherwise it will be 1, 2, 3.

4^k(8m+7)

``````class Solution {
public:
int numSquares(int n)
{
while(!(n&3)) n /= 4;
if(n%8 == 7) return 4;
for(int a = sqrt(n); a > 0; --a)
{
int b = sqrt(n-a*a);
if(a*a+b*b == n) return !b? 1 : 2;
}
return 3;
}
};``````

• Can u explain this please?

• Using DP as a hack, because it can store the essential info for us that we do not need to re-calculate it. In this case, we store the minimal `numSquare` for each number we encountered and then due to `static` feature, it will be not necessary for us to re-calculate it next time when we invoke this function. As for the searching process (to looking for the minimal `numSquare`), I think it's quite straight-forward and simple, since we have to check the searched numbers `a-i*i` to determine the current minimum, that's exactly why we should use DP here, `static` here is a trick.

• Awesome, thank you!

• Sure thing, dude!

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