力扣 --- 爬樓梯（動态規劃）

題目

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

示例 1：

輸入： 2

輸出： 2

解釋： 有兩種方法可以爬到樓頂。

1. 1 階 + 1 階
2. 2 階

示例 2：

輸入： 3

輸出： 3

解釋： 有三種方法可以爬到樓頂。

4. 1 階 + 1 階 + 1 階

5. 1 階 + 2 階

6. 2 階 + 1 階

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/climbing-stairs

爬樓梯作為動态規劃的經典題，也是值得掌握的。

方法一

如果我們直接看題目，似乎可以直接進行遞歸求解：

var climbStairs = function(n) {
    let sum = 0;
    const ref = function(n){
    	//方案不可行
        if(n < 0){
            return ;
        }
        //走到頭，方案+1
        if(n == 0){
            sum ++;
            return;
        }
        //以一步的情況
        ref(n - 1);
        //以兩步的情況
        ref(n - 2);
    }
    ref(n);
    return sum;
};
           

但這個是通過題目的意思，直接進行求解，并沒有什麼便利。

但是看題目我們可以推導出：

f(n) = f(n-1) + f(n -2);

其實也不難了解，我每次到n層台階，那麼一定是從n-1層台階或者n-2層台階上去的。

也就是說n層台階的方法總數應該是n-1和n-2層的總和。

如果想到這裡那麼這道題就可以轉換成斐波那契數列的問題了。

方法二

var climbStairs = function (n) {

      if (n == 1) {
        return 1;
      }
      if (n == 2) {
        return 2;
      }
      return climbStairs(n - 1) + climbStairs(n - 2)
    };
           

通過遞歸的方式進行求解

方法三

var climbStairs = function (n) {
      let p1 = 1, p2 = 2, p3 = 0;
      if (n == 1) {
        return 1;
      }
      if (n == 2) {
        return 2;
      }
      for (var i = 3; i <= n; i++) {
        p3 = p1 + p2;
        p1 = p2;
        p2 = p3;
      }
      return p3
    };
           

通過循環的方式來做。