題目說明:給一個n階的梯子，一次只能走一步或兩步，請問有多少種走法能走到n階

Case 1
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Case 2
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

這題我用了一個比較偷吃步的方式去解題，就是先把測資帶入然後去尋找規律(因為這題在題目分類時被標記在dynamic programming，所以用測資分別去帶一定可以找到其規律)，以下是我用帶入幾個測資之後的結果

Steps(n) Output
1 1
2 2
3 3
4 5
5 8

所以帶入五個後可以寫成以下的式子
f(n)=n, if n<=2 f(n)=f(n-1)+f(n-2), if n>2
*其實就是費氏數列的概念

看到這種式子很容易讓我們直覺使用遞迴的方式進行解題，但是最後提交的時候會發現超時，因為遞迴進行呼叫時會在記憶體運用大量堆疊來記錄其狀態，所以才會使用dynamic programming進行解題。

附上程式碼以及註解

Java

class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        int[] res = new int[n];//建立一個長度為n的array來儲存結果
        res[0] = 1;
        res[1] = 2;
        for(int i = 3; i <= n; i++) {
            res[i-1] = res[i-2] + res[i-3];//將剛才的遞迴式子用array儲存
        }
        return res[n-1];
    }
}

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        if n<=2:
            return n
        else:
            c=[0,1,2]
            for i in range(3,n+1):
                c.append(c[i-2]+c[i-1])
            return c[n]