動態規劃

• 思路：
  • 使用遞歸比較容易理解， f(n) = f(n - 1) + f(n - 2)；
    • 到剩余1級臺階有 f(n - 1)，到剩余2級臺階有 f(n-2)；
    • 邊界情況是

      • n = 0, f(0) = 1
      • n = 1, f(1) = 1
      • n = 2, f(2) = 2

    • 遞歸代碼實現：

class Solution {
public:int climbStairs(int n) {if (n == 0) {return 1;}if (n == 1) {return 1;}if (n == 2) {return 2;}return climbStairs(n - 1) + climbStairs(n - 2);}
};

• 很遺憾的事 n = 44 時，反饋超時了；所以，需要將遞歸變換一下；
• 使用兩個變量來緩存前兩種情形的結果，根據轉移方程 f(n) = f(n - 1) + f(n - 2)，迭代 n 次即可；

class Solution {
public:int climbStairs(int n) {int p = 0;int q = 0;int result = 1;for (int step = 1; step <= n; ++step) {p = q;q = result;result = p + q;}return result;}
};