class Solution {
    //dp[]数组代表和为n的完全平方数的最少数量
    //递推公式
    // dp[i] = Math.min(dp[i],dp[i-j*j] + 1) for all j*j <= i;
    // 完全背包
    public int numSquares(int n) {
        // int[] dp = new int[n+1];
        // dp[0] = 0;
        // for(int i = 1; i <= n; i++) {
        //     int min = n;
        //     for(int j = 1;j*j <= i; j++) {
        //         min = Math.min(min,dp[i-j*j]);
        //     }
        //     dp[i] = min + 1;
        // }
        // return dp[n];
        int[] dp = new int[n + 1];
        Arrays.fill(dp,10001);
        dp[0] = 0;
       //dp[j] = Math.min(dp[j],dp[j-i*i] + 1);
       
       for (int i = 1; i*i<= n; i++) {
        for (int j = i*i; j <= n; j++) {
            dp[j] = Math.min(dp[j],dp[j- i*i] + 1);
        }
       } 
       return dp[n];
    }
}