```
class Solution {
public:
int numSquares(int n) {
if (n < 1) return 0;
vector<int> least_dp(n+1, INT_MAX);
int i = 0, j = 0, perfectNum = 0, end = 0;
least_dp[0] = 0;
for (i = 1; i <= n; ++i)
{
end = (int)sqrt(i);
for (j = 1; j <= end; ++j)
{
perfectNum = j * j;
if (least_dp[i] > (1 + least_dp[i - perfectNum]))
least_dp[i] = 1 + least_dp[i - perfectNum];
}
}
return least_dp[n];
}
};
```