public class Solution {

```
public int NumSquares(int n) {
int[] dp = new int[n+1];
for( int j = 0; j <= n; j++){
int tmp = (int)Math.Sqrt(j);
if(tmp*tmp == j){
dp[j] = 1;
continue;
}
int minRes = Int32.MaxValue;
for(int i = 1; i <= tmp; i++){
minRes = Math.Min(minRes, dp[j-i*i]+1);
}
dp[j] = minRes;
}
return dp[n];
}
```

}