# 70. Climbing Stairs

## 題目概要
- 給定一個正整數 n，每次只能走一步或兩步，找出走到第 N 階共有幾種方法。(1 <= n <= 45)

Example 1:

Input: n = 2
Output: 2

Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 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

## 解題技巧
- n = 0 或者 n = 1，都只有一種走法，n = 2 時可以是 1 + 1 或者直接走 2 步，所以是兩種方法；n = 3 時可以是：
- 先走一步 (3 – 1) = 2 => 2 又會回到 n = 2 有兩種走法的情況
- 先走兩步 (3 – 2) = 1 => 1 又會回到 n = 1 有一種走法的情況

所以可以根據以上規律我們會優先推斷出可以用遞迴來解。

用遞迴解的話程式碼如下：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n == 0) return 1;
    if (n == 1) return 1;
    return climbStairs(n - 1) + climbStairs(n - 2);
};

但如果用 LeetCode submit 的話會***完美超時(Time Limit Exceded)***，所以得用迭代取代遞迴來解。

## 程式碼

var climbStairs = function(n) {
    let arr = [];
    arr[0] = 1;
    arr[1] = 1;
    for(let i = 2; i <= n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[n];
};