劍指offer：（七）斐波那契數列

一、題目描述

大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0）。

n<=39

二、解題分析：

1.可以采用遞歸的方法，但是缺陷是效率太差，可能導緻系統棧溢出；

2.建立一個數組，數組中相應下标存放斐波那契相應元素的值，這些值由arr[index-1]+arr[index-2]計算出來。

三、具體代碼：

public class Solution {
    public int Fibonacci(int n) {
        int[]fib=new int[n+1];
        fib[0]=0;
        if(n>0)fib[1]=1;
        
        for(int i=2;i<=n;i++){
           fib[i]=fib[i-1]+fib[i-2];
        }
        
        return fib[n];
//遞歸方法：不建議使用
 //   private int Fib(int n){
 //       if(n==1)return n;
 //       return Fib(n-2)+Fib(n-1);
    }
}
           

注：關于劍指offer的代碼後續會整理存放在我的Github上，有需要的同學可以自行Fork,如果覺得還不錯，可以打個☆Star哦~~~