題目:

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

你可以一次爬1或2階樓梯,那爬n階樓梯的方式有幾種

我們可以把方法歸類成兩種,最後一步爬一階跟最後一步爬二階
即爬n-1階的方法數+爬n-2階的方法數加起來就是爬n階的方法數
我們可以列式:f(n)=f(n-2)+f(n-1)
我們發現這其實就是個類費波那契數列（Fibonacci sequence）的結構
只要知道f(1),f(2)就能推斷出其他f(n)
而我們知道f(1)=1(一次一階),f(2)=2(一次二階和兩次一階)便可以開始實作了

class Solution:
    def climbStairs(self, n: int) -> int:
        ans=[1,2]
        for i in range(2,n):
            ans.append(ans[-1]+ans[-2])
        return ans[n-1]

建立一個陣列,第n項即代表f(n)的值
先將f(1),f(2)放入陣列,之後append的新項為末兩項和
直到append到第n項(即得知了我們要的f(n))
就回傳我們算出的f(n)值
不用遞迴是因為複雜度來到O(2^n),容易超時
最後執行時間24ms(faster than 98.81%)

那我們下題見