Given a positive integer n, find the least number of perfect square numbers (for example, `1, 4, 9, 16, ...`) which sum to n.

For example, given n = `12`, return `3` because `12 = 4 + 4 + 4`; given n = `13`, return `2` because `13 = 4 + 9`.

e.g. 12的DP表

 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 1 2 3 4 2 1 2 3 3

C++ Solution

``````
class Solution {
public:
int w[100000];
int DP[100000];
int numSquares(int n) {
int wi = sqrt(n) + 1;
int tempMinNum;
DP[0] = 0;

for(int i = 2; i &lt;= wi; ++i)  w[i - 1] = pow(i, 2);

for(int i = 1; i &lt;= n; ++i)
{
int minNum = (1&lt;&lt;31) - 1;

for(int j = 1; j &lt;= wi; ++j)
{
if(i &lt; w[1]) { DP[i] = DP[i - 1] + 1; break; }
if(i &lt; w[j]) { DP[i] = minNum; break; }
tempMinNum = min(DP[i - w[j]] + 1, DP[i - 1] + 1);
if(tempMinNum &lt; minNum) minNum = tempMinNum;
}
}
return DP[n];
}
};
``````

Update on 2/18/2016

``````
int DP[10000];
bool precom = true;

class Solution {
public:
int w[10000];
int numSquares(int num) {
if(!precom) return DP[num];

int n0 = 10000;
int wi = sqrt(n0) + 1;
int tempMinNum;
DP[0] = 0;

for(int i = 1; i <= wi; ++i)
w[i - 1] = pow(i, 2);

for(int i = 1; i <= n0; ++i)
{
int minNum = 2147483647;

for(int j = 1; j <= wi; ++j)
{
if(i < w[1]) { DP[i] = DP[i - 1] + 1; break; }
if(i < w[j]) { DP[i] = minNum; break; }
tempMinNum = min(DP[i - w[j]] + 1, DP[i - 1] + 1);
if(tempMinNum < minNum) minNum = tempMinNum;
}
}
precom = false;
return DP[num];
}
};
``````