279. 完全平方數(shù)

1.思路

1.1動態(tài)規(guī)劃:

這個題很容易就想到了動態(tài)規(guī)劃.每次F[n]=min{F[i]+F[j],i+j=n}

那么按照屈婉玲老師的三步走,直接解題:

1.建模, 2.子問題優(yōu)化, 3.規(guī)約公式

1.建模

①解:<x1,x2...xn>代表了Xi代表了i的選擇次數(shù)
②目標函數(shù):所有的i選擇次數(shù)加起來最少,且數(shù)量最少
③約束條件:所有的數(shù)字加起來等于n

2.子問題優(yōu)化

我如果選用數(shù)字i,那么原問題就變成了 F[n]=F[i]+F[n-i];

那么我要不要 i 呢?比較F[n] 分成F[1]+F[n-1],F[2]+F[n-2]...等之間的大小關(guān)系,從中選出最優(yōu)解

3.歸結(jié)公式

1.2動態(tài)規(guī)劃代碼

class Solution {
    public int numSquares(int n) {
       int[] f = new int[n+1];
       for(int i=1;i<n+1;i++){
           if((int)Math.pow((int)Math.pow(i,0.5),2)==i)f[i]=1;  //當Ｎ開方是整數(shù)
           else{　　　　　　　　　　　　//當根號N不是整數(shù)
               f[i] = Integer.MAX_VALUE;     //從數(shù)字中選擇最小的
               for(int j=1;j<=i/2;j++){
                   if(f[j]+f[i-j] < f[i]){
                       f[i] = f[j]+f[i-j];
                   }
               }
           }
       }
       return f[n];
    }
}

結(jié)果

總結(jié):效果不好,在于循環(huán)的次數(shù)太多了

2.1四平方數(shù)定理

image.png

參考地址:https://blog.csdn.net/l_mark/article/details/89044137

2.2代碼

class Solution {
   public int numSquares(int n) {
       while(n%4==0)n/=4; //因為如果這個數(shù)是4的倍數(shù),先去除所有的4剩下的部分就能計算是否為(8b+7)
       if(n%8==7)return 4;
       if((int)Math.pow((int)Math.sqrt(n),2) == n)return 1;
       for(int i=1;i*i<=n/2;i++){
           int cost = (int) Math.sqrt(n-i*i);
           if(cost*cost + i*i == n)return 2;
       }
       return 3;
    }
}

image.png