I camp up with a DP solution in Java.

#### DP Solution （33ms）

```
public int numSquares(int n) {
int state[] = new int [n+1];
int temp = 0;
int maxSquare = (int) Math.sqrt(n);
int positive;
state[0] = 1;
for(int i=0;i<=n;i++){
state[i] = Integer.MAX_VALUE;
}
for(int i=0;i<=maxSquare;i++){
state [i*i] = 1;
}
for(int i=1;i<=maxSquare;i++){
positive = i*i;
for(int j=positive;j<=n-positive;j++){
if (state[j]+state[positive]
<state[j+positive]) {
state[j+positive]
= state[j]+state[positive];
}
}
}
return state[n];
}
```