力扣 --- 爬楼梯（动态规划）

题目

假设你正在爬楼梯。需要 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
    };
           

通过循环的方式来做。