斐波那契数列

从 斐波那契 数列 入门动态规划

什么是斐波那契数列？

假设斐波那契数列用 F 来表示, 那么 F(0)=1, F(1)=1， 且当 n>=2 时：F(n)=F(n-1)+F(n-2)。

比如计算 F(4)， 可以用下面这幅图来表示：

计算 F(4)，需要向下计算 F(3) 和 F(2), 而计算 F(3) 又需要计算 F(2) 和 F(1)。可以看到 F(2) 被重复计算了。假设 计算 F(n) 的 n 很大，那么将有大量的中间数据被重复计算。那么如果我们用额外的一个数组去存储已经被计算过的变量，则会避免上述说的冗余计算。

什么是动态规划？

将一个大问题将拆分成许多重叠的在子问题，在求解子问题的过程中保留子问题的答案，使得每一个子问题只求解一次，最终获得原问题的答案。这就是动态规划。

一般动态规划有两种求解思路，一种是自顶向下解决，另一种是自顶向上解决。由于不涉及重复计算，所以两种思路的时间复杂度和空间复杂度均相同。一般来说，自顶向下的求解思路更加自然和容易被想到。

自顶向下求斐波那契数列

 //自顶向下递归, 使用记忆化搜索进行剪枝
public class FibonacciSeq {

    int[] memo;//用来存储已经计算好了的斐波那契数列

    FibonacciSeq(int n){
        memo=new int[n+1];
        for (int i = 0; i < memo.length; i++) {
            memo[i]=-1;
        }
    }

    public int fib(int n){
        if (n==0){
            return 0;
        }
        if (n==1){
            return 1;
        }

        if (memo[n]==-1){
            memo[n]=fib(n-1)+fib(n-2);
            return memo[n];
        }else {
            return memo[n];
        }
    }

    public static void main(String[] args) {
        int n=50;
        FibonacciSeq fbsq=new FibonacciSeq(n);

        long startTime=System.nanoTime();
        fbsq.fib(n);
        long endTime=System.nanoTime();
        double time=endTime-startTime;

        System.out.println("fib"+n+"花费时间"+time/1000000000.0+"秒");
    }


}

自底向上求斐波那契数列

// 自底向上解决问题
public class FibonacciSeq2 {

    int[] memo;//用来存储已经计算好了的斐波那契数列

    public int fib(int n){
        memo=new int[n+1];

        memo[0]=0;
        memo[1]=1;

        for (int i=2;i<=n; i++){
            memo[i]=memo[i-1]+memo[i-2];
        }

        return memo[n];
    }

    public static void main(String[] args) {
        int n=50;
        FibonacciSeq2 fbsq=new FibonacciSeq2();

        long startTime=System.nanoTime();
        fbsq.fib(n);
        long endTime=System.nanoTime();
        double time=endTime-startTime;

        System.out.println("fib"+n+"花费时间"+time/1000000000.0+"秒");
    }

}

经过运行发现，无论是自顶向下还是自底向上，运行的时间都没有明显的区别。