```
public class Solution {
public int numSquares(int n) {
int square_root=1;
int[] dp = new int[n+1];
for(int i = 1;i<n+1;i++){
if(i == square_root*square_root){
dp[i] = 1;
square_root+=1;
}else{
int min = i;
for(int j = square_root-1;j>0;j--)
min = Math.min(min,1+dp[i-j*j]);
dp[i] = min;
}
}
return dp[n];
}
}
```