class Solution {
    public int numSquares(int n) {
		int[] dp = new int[n + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		for (int i = 1; i * i <= n; i++) {
			dp[i * i] = 1;
		}
		for (int i = 2; i <= n; i++) {
			for (int j = 1; j <= i / 2; j++) {
				dp[i] = Integer.min(dp[i], dp[j] + dp[i - j]);
			}
		}
		return dp[n];
    }
}