在這篇文章中，我們來探討 Leetcode 第 70 題「Climbing Stairs」。這道題目是一個經典的動態規劃問題，經常作為學習 DP（動態規劃）的入門題。題目的要求是：假設你站在樓梯底部，每次你可以爬 1 步或 2 步，問你到達樓梯頂部有多少種不同的方式。

題目：
給定一個正整數 n，表示樓梯的總步數。每次你可以選擇爬 1 步或 2 步，問爬到樓梯頂部的總共方式數。

解題思路

先列出幾回合來找規律：

Input n = 1, Output = 1 種
1 step

Input n = 2, Output = 2 種
1 step + 1 step
2 steps

Input n = 3, Output = 3 種
(1 step + 1 step) + 1 step
(1 step) + 2 steps
(2 steps) + 1 step

Input n = 4, Output = 5 種
(1 step + 1 step + 1 step) + 1 step
(1 step + 2 steps) + 1 step
(2 steps + 1 step) + 1 step
(1 step + 1 step) + 2 steps
(2 steps) + 2 steps

從 output 的值，我們可以觀察到規律，

假設樓梯有 4 階 (n = 4)，你需要找出總共有多少種方法可以到達第 4 階。
如果你已經在第 3 階了，你只需要走 1 步就能到第 4 階。
如果你已經在第 2 階了，你只需要走 2 步就能到第 4 階。

這樣我們可以得出一個結論：要到達第 4 階的總方法數等於：
從第 3 階到第 4 階的方法數，加上從第 2 階到第 4 階的方法數。

其實就是一個費式數列，到達第 n 階的方法總數等於到達第 n-1 階的方法數，加上到達第 n-2 階的方法數
唯一的差別是起始條件。

先實做遞迴版本，

class Solution {
public:
    int climbStairs(int n) {
        //if (n == 1) return 1;
        //if (n == 2) return 2;
        if (n <= 2) return n;

        return climbStairs(n-1) + climbStairs(n-2);
    }
};

結果 leetcode 顯示 Time Limit Exceeded，
原因是因為重複計算太多次了。
以 Fib(5) 為例，畫出遞迴樹來展示費事數列的遞迴過程，可以發現 Fib(3) 計算了2次，Fib(2) 計算了3次，很多子問題被重複計算了，這種版本在計算 n = 40 以上就會花費很多時間。

                 Fib(5)
                /     \
           Fib(4)      Fib(3)
          /     \      /     \
     Fib(3)   Fib(2) Fib(2)  Fib(1)
     /    \      |      |      
Fib(2)  Fib(1)   1      1
  |        |
  1        1

改進的方法是讓這個遞迴版本能夠有記憶，

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+1); // 預設值為 0
        return climbStairs(n, dp);
    }
private:
    int climbStairs(int n, vector<int>& dp) {
        //if (n == 1) return 1;
        //if (n == 2) return 2;
        if (n <= 2) return n;

        if (dp[n] == 0) // 假如是預設值的話
            dp[n] = climbStairs(n-1, dp) + climbStairs(n-2, dp);

        return dp[n];
    }
};

改成迭代版本，

class Solution {
public:
    int climbStairs(int n) {
        //if (n == 1) return 1;
        //if (n == 2) return 2;
        if (n <= 2) return n;

        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

時間複雜度 O(n)
空間複雜度 O(n)

由於每次計算 dp[n] 只依賴於前兩個狀態，因此我們不需要存下全部結果到 vector，去掉 vector，優化成空間複雜度 O(1)，

class Solution {
public:
    int climbStairs(int n) {
        //if (n == 1) return 1;
        //if (n == 2) return 2;
        if (n <= 2) return n;

        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = first + second;
            first = second;
            second = tmp;
        }
        return second;
    }
};

時間複雜度 O(n)
空間複雜度 O(1)

參考：
#70. Climbing Stairs