斐波那契数

f(0)=0
f(1)=1
f(n) = f(n-1)+f(n-2)  //n>=2

递归法

时间复杂度： O(2^n)，效率极其低下

int f(int n){
   //check n >=0
   if(n==0) return 0;
   if(n==1) return 1;

   return f(n-1)+f(n-2); 
}

正推法

一次求取 f(0),f(1),f(2),f(3),...,f(n)

时间复杂度为： O(n)

int f(int n){
    // check n>=0
    if(n==0) return 0;
    if(n==1) return 1;

    int[] arr = new array[n+1];
    arr[0]=0;
    arr[1]=1;
    for(int i=2;i<=n;i++){
        arr[i]=arr[i-1] + arr[i-2];
    }
    return arr[n];
}

上面还可以进行优化，没必要设置数组大小为n+1，只需要3个就可以了；

优化后的代码：

int f(int n){
    //check n >=0
    if(n==0) return 0;
    if(n==1) return 1;

    int[] arr=new arr[3];
    arr[0]=0;
    arr[1]=1;

    for(int i=2;i<=n;i++){
        t=i%3;
        t1=(i-1)%3;
        t2=(i-2)%3;
        arr[t]=arr[t1] + arr[t2];
    }
    return arr[n%3];
}

打表法

提前算好结果：

result[0]=0
result[1]=1
result[2]=1
result[3]=2
result[4]=3
result[5]=4
...

时间复杂度为：O(1)