題目

題目說他會給一個整數n，然後我們要算出第n個的費波那契數回傳給他

想法

圖片來源:http://www.mathsgreat.com/fibon/fibon.html

費波那契數列是從0和1開始的數列，費波那契數就是後續的數字都是前兩項相加，他是以遞迴的方式計算的。
數學公式就是，F(n)=F(n-1)+F(n-2),F(0)=0,F(1)=1，

認識完費波那契數之後就會覺得這題是不是很熟悉，跟我們的上一題Climbing Stairs幾乎一模一樣，只是題目的敘述換了一個故事。
為什麼我會覺得一樣呢，因為爬樓梯那題我找方法數的方式也是前兩項相加會等於我要的答案，只是爬樓梯是從第一階開始，所以初始值會是1跟2，而我們這題的費波那契數是從0跟1開始。
所以我們只要把上一題的程式碼偷過來，改一下初始值就會成功了喔!

程式碼

class Solution {
    public int fib(int n) {
        
        if(n<=1) return n;
   
        //動態規劃的初始值
        int prev1 =1; //f(n-1)
        int prev2 =0; //f(n-2)
        
        for(int i=2;i<=n;i++){
            int current =prev1+prev2; //當前結果
            prev2=prev1; //更新f(n-2)
            prev1=current;//更新f(n-1)
        }
        return prev1;
    }
}

執行成功畫面