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 = ai*i;
t = min(t, !b? 1 : 1+v[b]);
}
v.push_back(t);
}
return v[n];
}
};
DP solution using static to accelerate from 324ms to 12ms in C++

If you don't know Lagrange's foursquare 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(na*a); if(a*a+b*b == n) return !b? 1 : 2; } return 3; } };

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