---
# System prepended metadata

title: Untitled

---

Leedcode 70.Climbing Stairs
首先，先講這題主要觀念，輸入n個階梯，輸出N(1or2) 找出使n成立的方法數。
例:1格階梯 只有一種方法能做
   2格階梯 有11 2 兩種方法能做
   3格階梯 就會變成有12 21 111 三種方法能做
4格階梯 就會有1111 112 121 211 22 五種方法能做...

我們會看出一個規律，當我們要求出n有幾種方法時，n的方法數會是前兩個(n-1)+(n-2)的方法數相加。

1.一般遞迴
![](https://i.imgur.com/yWsyvDz.png)
用時間複雜度O(n)方法速度會很慢，時間過長就會TLE。
        
2.遞迴記憶
![](https://i.imgur.com/UmBuFPZ.png)
這種方法跟前一種十分類似，但是是將每次答案儲存在陣列裡，最後再輸出出來，就不會使程式跑爆。

3.迴圈
![](https://i.imgur.com/f0oSPbk.png)
時間複雜度O(log n)在我的三個方法裡時間消耗最少，記憶體也是最少的，在迴圈裡將答案跑出來再輸出值。