[数据结构与算法]斐波拉数列的引出

求解斐波那契数列例子。求一个问题的解需要用到之前的数据，依次递归。

解决方法（以斐波那契数列为例）：

1、纯递归实现，问题是需要不停的递归，时间复杂度高

public static int Fibonacci_recursive(int n){
        if(n<=0){
            return 0;
        }else if(n==1){
            return 1;
        }
        else{
            return Fibonacci_recursive(n-1)+Fibonacci_recursive(n-2);
        }
    }

2、递归+动态规划，自顶向下。求出来的值存放起来，已备下次重复使用。

public static int Fibonacci_D(int n){
        int[] Fibonaccis=new int[n];
        for(int i=0;i<n;i++){
            Fibonaccis[i]=-1;
        }
        return Fibonacci_DD(Fibonaccis,n);
        
    }
    public static int Fibonacci_DD(int[] nums,int n){
        if(n<=0){
            return 0;
        }else if(n==1){
            return 1;
        }
        if(nums[n]!=-1){//如果该结果已有，则直接使用。
            return nums[n];
        }else{//没有调用递归
           nums[n]=Fibonacci_DD(nums,n-1)+Fibonacci_DD(nums,n-2);
        }
        return nums[n];
    }

3、动态规划，自底向上。先求出问题最开始的解，由前往后。最终求出答案。

public static int Fibonacci_DownTop(int n){
    int[] fibonaccis =new int[n];
    fibonaccis[0]=0;
    fibonaccis[1]=1;
    for(int i=2;i<n;i++){
        fibonaccis[i]=fibonaccis[i-1]+fibonaccis[i-2];
    }
    return fibonaccis[n-1];
}