$ cat ./coding/70-climbing-stairs.md

────────────────────────────────────────────────────────────

70. Climbing Stairs

題目的思路在於，當前這個位置可以兩個地方跳上來，第一種是來自從兩階之外，跳了兩階上來，另一種是自一階之外，跳了一階上來。

換句話說如果兩階之外的那個階梯，有 k 種方式達到，一階之外的階梯有 w 種方式達到，當前的位置就有 k + w 種達到的方式。

我在思考的時候有去想了一下這個問題，那就是要不要加一呢？所以想分享我的想法。

在算幾種方法的時候，如果我們只考慮一次只能走一階，其實走到 n 階也是只有一種走法，因為我們每次都是「加一」，這個題目會這樣問，是因為其餘的排列組合都是是透過不同的走法來走到的，並不是靠走了幾階去走到的。

上面的想法就可以用數學表達式來表達：$f(n)=k+w$

其中 k 又可以是 $f(n-2)$，w 又可以是$f(n-1)$，替換後的數學表達式為：$f(n)=f(n-2)+f(n-1)$

整個題目等同於 509. Fibonacci Number

但是要特別注意的是，到底最後 n 階，在斐波那契數所表達的 n 在這個題目的 n 為何？

class Solution:
    def fib(self, n: int) -> int:
        memo = [0] * (n+1)
        memo[1] = 1
        for i in range(2, n+1):
            memo[i] = memo[i-1] + memo[i-2]

        return memo[n]

$ ls ./coding/ | grep -v 70-climbing-stairs