279. perfect square

Complete square

Give you an integer n , return And for n The minimum number of complete squares of .

Complete square It's an integer , Its value is equal to the square of another integer ; let me put it another way , Its value is equal to the product of the self multiplication of an integer . for example ,1、4、9 and 16 They're all perfect squares , and 3 and 11 No .

Example 1：

Input ：n = 12
Output ：3
explain ：12 = 4 + 4 + 4
Example 2：

Input ：n = 13
Output ：2
explain ：13 = 4 + 9

Tips ：

1 <= n <= 104

reflection

I think this question is actually better than the last one I did 322. Change for It's simpler ,

Because there is no non-existent situation , Because there is omnipotence 1 The existence of , You can make up as much as you like ！

I think this is just one more step and I need to figure it out by myself ,n The complete square within , It can be converted into an and 322. Change for Similar questions , And it's easier to think about less ！

First, the first question , How do we ask n Complete square within

      // step 0  seek n The complete square within 
        int[] square=new int[n/2];
        int l=1;
        square[0] = 1;
        for (int i=2;i<n;i++){
    
            if(i*i>n) break;
            square[i-1] = i*i;
            l++;
        }

It turns into 01 knapsack problem , hypothesis n=12, Its The full square array is x={1,2,4,9}

In fact, it is to use {1,2,4,9} The least number in it is to fill it up 12 that will do !

Definition dp Array and its subscript meaning

dp[j] : Indicates that a complete square array is used to fill up j The minimum number of complete squares used

initialization dp Array

dp[0]=0; Guarantee dp[j-x[i]] x[i]==j when dp[j] = 1;

dp[1]=1;

rest dp[j] = Integer.Max;

State transition equation

Traverse x, Choose the smallest dp[j] = dp[j - x[i]]

public int numSquares(int n) {
    
        // step 0  seek n The complete square within 
        int[] square=new int[n/2];
        int l=1;
        square[0] = 1;
        for (int i=2;i<n;i++){
    
            if(i*i>n) break;
            square[i-1] = i*i;
            l++;
        }
        if(l<=1) return n;

        // step 2  establish dp Array 
        int[] dp=new int[n+1];

        // step 3  initialization dp Array 
        dp[0]=0;
        dp[1]=1;
        for (int i=2;i<dp.length;i++){
    
            dp[i] =Integer.MAX_VALUE;
        }

        // step 4  perfect dp Array 
        for (int j=2;j<dp.length;j++){
    
            for (int num : square){
    
                if(num<=j){
    
                    dp[j]=Math.min(dp[j],dp[j-num]+1);
                }
            }
        }

        // print Dp
        for (int i=0;i<dp.length;i++){
    
            System.out.println("dp "+i+","+dp[i]);
        }
        return dp[dp.length-1];
    }

Advanced

Its acquisition >n The complete square of , It can be done in a loop

    public int numSquares2(int n) {
    
        


        // step 2  establish dp Array 
        int[] dp=new int[n+1];

        // step 3  initialization dp Array 
        dp[0]=0;
        dp[1]=1;
        for (int i=2;i<dp.length;i++){
    
            dp[i] =Integer.MAX_VALUE;
        }

        // step 4  perfect dp Array 
        for (int j=2;j<dp.length;j++){
    
        //step 0  seek n The complete square within 
            for (int i=1;i*i<=j;i++){
    
                int num=i*i;
                if(num<=j){
    
                    dp[j]=Math.min(dp[j],dp[j-num]+1);
                }
            }
        }

        // step 5 print Dp
        for (int i=0;i<dp.length;i++){
    
            System.out.println("dp "+i+","+dp[i]);
        }
        return dp[dp.length-1];
    }