279. 完全平方数

279. 完全平方数

1.思路

1.1动态规划:

这个题很容易就想到了动态规划.每次F[n]=min{F[i]+F[j],i+j=n}

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

1.建模, 2.子问题优化, 3.规约公式

1.建模

①解:<x1,x2...xn>代表了Xi代表了i的选择次数
②目标函数:所有的i选择次数加起来最少,且数量最少
③约束条件:所有的数字加起来等于n

2.子问题优化

我如果选用数字i,那么原问题就变成了 F[n]=F[i]+F[n-i];

那么我要不要 i 呢?比较F[n] 分成F[1]+F[n-1],F[2]+F[n-2]...等之间的大小关系,从中选出最优解

3.归结公式

1.2动态规划代码

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;  //当Ｎ开方是整数
           else{　　　　　　　　　　　　//当根号N不是整数
               f[i] = Integer.MAX_VALUE;     //从数字中选择最小的
               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];
    }
}

结果

总结:效果不好,在于循环的次数太多了

2.1四平方数定理

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; //因为如果这个数是4的倍数,先去除所有的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