剛剛我在寫 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 的職業病（