public class Solution {
    /**
     * @param n a positive integer
     * @return an integer
     */
    public int numSquares(int n) {
        // Write your code here
        int[] dp = new int[n + 1];
        // 将所有非平方数的结果置最大，保证之后比较的时候不被选中
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 将所有平方数的结果置1
        for (int i = 0; i * i <= n; i++) {
            dp[i * i] = 1;
        }
        
        // 从小到大找任意数a
        for (int i = 0; i <= n; i++) {
            // 从小到大找平方数bｘb
            for (int j = 1; i + j * j <= n; j++) {
                // 因为a+b*b可能本身就是平方数，所以我们要取两个中较小的
                dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j]);    
            }
        }
        
        return dp[n];
    }
}