The following is my code. For n = 6, VS returns 3, but OJ returns 1.

public int NumSquares(int n) {

```
if (n <= 3) return n;
int[] dp = new int[n+1];
int i;
for (i = 0; i <= 3; ++i) dp[i] = i;
for (i = 4; i <= n; ++i) {
dp[i] = dp[i-1] +1;
for (int j = (int) Math.Sqrt(i); j*j*dp[i] > i; --j) {
if (i % j*j == 0) {
dp[i] = i/ (j*j);
}
else {
dp[i] = Math.Min(dp[i], dp[i-j*j] + 1);
}
}
}
return dp[n];
}
```