題目

題目說有一個樓梯總共有n階，我每次可以爬1階或2階。那我們要算出總共有幾種不同的走法可以到第n階呢。

想法

因為之前有解過類似的數學題，所以就想說先畫圖找規律，然後畫到第五個的時候發現，四階的方法數=二階+三階的方法數，五階的方法數=三階+四階的。
所以我想說我先設兩個變數來代表一階跟二階的方法數，然後從第三階開始算到n，然後每次算完都把後面的變數值移到前面的變數，然後更新後面的變數值=剛剛算的方法數。
這樣以此類推一直算到n階。

程式碼

class Solution {
    public int climbStairs(int n) {
        //f(2)=2 
        //f(1)=1
        if(n==2) return 2;
        if(n==1) return 1;
   
        //動態規劃的初始值
        int prev1 =2; //f(n-1)
        int prev2 =1; //f(n-2)
        //從第三階開始計算
        for(int i=3;i<=n;i++){
            int current =prev1+prev2; //當前結果
            prev2=prev1; //更新f(n-2)
            prev1=current;//更新f(n-1)
        }
        return prev1;
    }
}

執行成功畫面