輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n];//dp[i]表示在到第i層有dp[i]種方法
        if (n <= 2)
            return n;
        dp[0] = 1;
        dp[1] = 2;
        
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
}
/**
動態規劃題目：
1. 確定dp數組
2. dp數組初始化
3. 確定遍歷順序
4. 模擬遍歷*/

class Solution {
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        else if(n==2){
            return 2;
        }
        else {
            int r=0;
            int p=1;
            int q=2;
            for(int i=3;i<=n;i++){
                r=p+q;
                p=q;
                q=r;
            }
            return r;
        }

       
    }
}

class Solution {
    public int climbStairs(int n) {
        // 方法一：動態規劃
        // 定義dp數組
        int[] dp = new int[n + 1]; // 要走到第n階樓梯所以要定義 n + 1, dp[i]表示要走到第i個階梯對應的方法數
        // dp數組初始化
        dp[0] = 1;
        dp[1] = 1; // 走到第一個階梯有1種方法
        // 遍歷遞歸
        for(int i = 2; i <= n; i++) {
            // 狀態轉移方程
            dp[i] = dp[i - 1] + dp[i - 2]; // 可以從第一階樓梯走到也可以從第二階樓梯走到
        }
        // 這是一個狀態轉移問題，狀態為在不同樓梯上的狀態
        return dp[n];
    }
}