```
class Solution {
public:
int numSquares(int n){
vector<int> dp(n+1,0), squares{};
for (int i=1; i*i<=n; ++i) squares.push_back(i*i);
for (int i=0; i<=3; ++i) dp[i]=i;
for (int i=4; i<=n; ++i){
int mini=INT_MAX;
for (auto &&x: squares){
int prev=i-x;
if (prev<0) break;
mini=min(mini,1+dp[prev]);
}
dp[i]=mini;
}
return dp[n];
}
};
```