class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2; //表示有兩個台階，有兩種爬法：一次爬一個台階，或者一次爬兩個台階，直接返回 2

        int[] a =  new int[n];
        a[0]=1; //代表爬 1 階樓梯的方法數為 1
        a[1]=2; //代表爬 2 階樓梯的方法數為 2

        for(int i=2;i<n;i++){
            a[i]=a[i-1]+a[i-2];
        }
        return a[n-1]; // 由於陣列索引是從 0 開始的，所以第 n 階樓梯的方法數對應到 a[n-1] 這個位置
    }
}

class Solution {
    public int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }
}