package DP;

public class Fibonacci {
    /**
     * 斐波那契数列初级
     * @param n
     * @return
     */
    public int RecursiveFibonacci(int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        return RecursiveFibonacci(n-1)+RecursiveFibonacci(n-2);
    }

    /**
     * 升级版
     */
    public int fibNacci0(int n){
        int[] tong=new int[n];
        if(n == 0||n==1){
            return 1;
        }
        tong[0]=1;
        tong[1]=1;
        for(int i = 2;i<n;i++){
            tong[i]=tong[i-1]+tong[i+1];
        }
        return tong[n-1];
    }

    /**
     * 再度升级版
     */
    boolean first=true;
    int[] fib;
    public int fibNacci(int n){
        if(first){
            first=false;
            fib = new int[n];
        }
        if(n==1) {
            return 1;
        }
        if(n == 2) {
            return 1;
        }
        if(fib[n]!=0){
            return fib[n];
        }
        return fib[n]=fibNacci(n-1)+fibNacci(n-2);
    }
/**
*最优化版
*/
    public int fibNacci2(int n){
        int a=0,b=1,sum=0,i;
        for(i=0;i<n;i++){
            sum=a+b;
            a = b;
            b = sum;
        }
        return sum;
    }
}