70. Climbing Stairs

題目：
爬樓梯，每次可走 1 或 2 步，共有幾種走法

範例：

• 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 階的方法數量 =

1. 從 n-1 階再走 1 步
2. 從 n-2 階再走 2 步

斐波那契數列：
f(n) = f(n-1)+f(n-2)

程式碼：

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n; //因為1=1種；2=2種（1+1/2）

        int first = 1;  // 到第一階的方法數
        int second = 2; // 到第二階的方法數

        // 從第三階開始，計算每一階的方法數
        for (int i = 3; i <= n; i++) {
            int third = first + second; // 第 i 階 = 前兩階方法數加起來
            first = second;             // 往前推一階
            second = third;             // 更新為新的方法數
        }

        return second; // 最後就是到第n階的方法數
    }
}

first → 記住 到前一階的方法數（f(n-2))
second → 記住 到上一階的方法數（f(n-1))
third → 計算 到現在這一階的方法數（f(n))

實際操作：

n = 5
first = 1 // f(1)
second = 2 // f(2)

STEP1:
i=3
third = first + second
= 1 + 2
= 3 // 第3階有3種走法

// 更新
first = second → first = 2
second = third → second = 3

STEP2:
i=4
third = first + second
= 2 + 3
= 5 // 第4階有5種走法

// 更新
first = second → first = 3
second = third → second = 5

STEP3:
i=5
third = first + second
= 3 + 5
= 8 // 第5階有8種走法

// 更新
first = second → first = 5
second = third → second = 8

結果：second 保存 f(5) = 8