剛剛我在寫 Leetcode 的 70. Climbing Stairs 沒留意到它是考 DP 寫成了 Recursion，結果跑起來 timeout。剛好我覺得這是一個很好的 Recursion vs DP 的範例，我就拿出來解釋一下好了。首先，這是我寫的 Recursion 解法：

class Solution {
public:
    int sol = 0;
    int climbStairs(int n) {
        f(n, 0); //把 sum 設為 0
        return sol;
    }
    
    void f(int n, int sum){
        if (sum > n) return; //超出了目標位置
        if (sum == n){
            sol++; //這是其中一個爬法
            return;
        }
        //跟終點還有點距離，試試
        f(n, sum+1); //爬一步
        f(n, sum+2); //爬兩步
    }
};

每爬一段之後，檢查是不是已經到終點了，如否，再分支出兩種走法 – 走一步 與 走兩步。

這個我覺得是最簡單易懂的寫法（甚至已經是教科書等級的 recursive function 了），但是居然跑到 timeout 這個我還真的沒想到。所以後來只好換成 space-time tradeoff 的 dynamic programming 寫法：

class Solution {
public:
    int climbStairs(int n) {
        int dp[46]; //因為題目說最多 n = 45
        dp[1] = 1; //爬到第一格，只有一個爬法就是爬一格
        dp[2] = 2; //爬到第二格，只有 1 + 1 跟 2 兩種爬法
        for(int i = 3; i <= n; i++){
            //從 3 開始，就是前兩格爬法的總和
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n]; // 最後回傳能爬到最後一格的總可能路線
    }
};

果然是做嵌入式開發做得多，寫出來都是以最佳化 memory consumption 的職業病（