动态规划求斐波那契数列

佚名 4年前 (2020-05-13) 算法 630人围观抢沙发百度已收录

1.递归方式

public static void main(String[] args) {
    long start=System.currentTimeMillis();
    System.out.println(start);
    System.out.println(fibonacci(50));
    long end=System.currentTimeMillis();
    System.out.println(end);
    System.out.println("用时："+(end-start)+"ms");
}

public static double fibonacci(int n){
   if(n==0){
       return 0;
   }
   if(n==1){
       return 0;
   }
   if(n==2){
       return 1;
   }
   return fibonacci(n-2)+fibonacci(n-1);
}

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

可以看到递归的方式，效率非常低，非常耗时，而且求大一点的数的时候，可能会直接溢出

2. 动态规划

public static void main(String[] args) {
    long start=System.currentTimeMillis();
    System.out.println(start);
    System.out.println(fibonacci(50));
    long end=System.currentTimeMillis();
    System.out.println(end);
    System.out.println("用时："+(end-start)+"ms");
}

public static double fibonacci(int n){
    if(n==0){
        return 0;
    }
    double [] temp=new double[n];
    temp[0]=0;
    temp[1]=1;
    if(n>1){
        for(int i=2;i<n;i++){
            temp[i]=temp[i-1]+temp[i-2];
        }
    }
    return temp[n-1];
}