public class Solution {
public int numSquares(int n) {
if (n <= 0) return 0;
int[] dp = new int[n+1];
for (int i = 0; i <= n; i++) {
dp[i] = i;
for (int j = 1; j*j <= i ; j++) {
dp[i] = Math.min(dp[i], 1 + dp[i  j*j]);
}
}
return dp[n];
}
}
Short Java DP solution

Nice solution! However in the inner loop, j does not have to start at 1. Start at 2 will get the same result but ~10% faster (103ms > 93ms).
public class Solution { public int numSquares(int n) { if (n <= 0) return 0; int[] dp = new int[n+1]; for (int i = 0; i <= n; i++) { dp[i] = i; for (int j = 2; j*j <= i ; j++) { dp[i] = Math.min(dp[i], 1 + dp[i  j*j]); } } return dp[n]; } }