---
# System prepended metadata

title: LeetCode 70. Climbing Stairs
tags: [Leetcode]

---

# LeetCode 70. Climbing Stairs
[LeetCode 70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/description/) (<font color=#00AF9B>Easy</font> 52.9%) 

<!-- 
(<font color=#00AF9B>Easy</font> 53.8%) 
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
 -->
    
- 限制 :

    <ul>
    <li><code>1 <= n <= 45</code></li>
    </ul>

- Solution
    這題其實就是費氏數列的變形，用費氏數列解就好。
    - 時間複雜度: $O(n)$
    - 空間複雜度: $O(n)$

- 程式碼
    ```c++=
    class Solution {
    public:
        int climbStairs(int n) {
           vector<int> record{1, 1};
           for(int i=2;i<=n;i++)
           {
                record.push_back(record[i-1] + record[i-2]);
           }
           return record[n];
        }
    };
    ```
</details>