算法-爬楼梯2

爬楼梯 2

难度：简单

描述：

一个小孩爬一个 n 层台阶的楼梯。他可以每次跳 1 步， 2 步或者 3 步。实现一个方法来统计总共有多少种不同的方式爬到最顶层的台阶

本题跟爬楼梯一毛一样，只是多了可以一次跳三步，所以尽量自己做出来

样例：

n = 3，1 + 1 + 1 = 2 + 1 = 1 + 2 = 3 = 3，共有 4 种方法

思路分析：

这类题我们首先要来找其中的规律，找到了里面的规律，剩下的就好办了。

我再列举出几个结果：

1: 1 // 1种方法
2: 1+1=2 // 2种方法
3: 1 + 1 + 1 = 2 + 1 = 1 + 2 = 3 = 3 // 4种方法
4: 1+1+1+1=2+2=1+3 =1+2+1=2+1+1 = 1+1+2= 3+1  // 7种方法
5：1 * 5 =1+2+2 =2+1+2 =2+2+1 = 1+1+3 =1+3+1 = 3+1+1 = 3+2 = 2+3 = 1+1+1+2 =1+2+1+1 = 2+1+1+1 = 1+1+2+1  // 13种方法

查找样例中的规律：爬楼梯

代码模板：

/**
 * @param n: An integer
 * @return: An integer
 */
const climbStairs2 = function(n) {};

想一想再看答案

规律

除了前 3 阶楼梯是没有规律的，第 n 阶的楼梯的方法是第 i-1 、第 i-2 和第 i-3 阶楼梯所用方法的和。

规律都给你总结好了，再给你个机会自己做出来。

代码：

解题的核心就是逐步推导，推导出 n 前面的两个值。

递归

因为做过一遍，最先想起来的就是递归。

const climbStairs2 = n => {
  let everyStairs = k => {
    // 循环退出条件
    if (k === 1) return 1;
    if (k === 2) return 2;
    if (k === 3) return 4;
    return everyStairs(k - 1) + everyStairs(k - 2) + everyStairs(k - 3); // 三个值相加求出k所用的方法
  };
  return everyStairs(n);
};
console.log('输出', climbStairs2(3), climbStairs2(4), climbStairs2(5));

交换变量

实际上我们只需要 n 之前的三个值，就可以求出 n 所用的方法，所以我们没必要将 n 之前的所有值都推导出来。

const climbStairs2 = k => {
  if (k === 1) return 1;
  if (k === 2) return 2;
  if (k === 3) return 4;
  let [a, b, c] = [1, 2, 4]; // 前三阶楼梯
  for (let i = 3; i <= n; i++) {
    [a, b, c] = [b, c, a + b + c]; // 交换变量 更新前两个值，推导k的值
  }
  return c;
};
console.log('输出', climbStairs2(3), climbStairs2(4), climbStairs2(5));

数组形式：

const climbStairs2 = function(n) {
  let dp = [0, 1, 2, 4]; // 初始数组 前面三个没有规律
  // 从第4阶楼梯开始推导   
  for (let i = 4; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; // 从3开始都是可以由前面3个元素相加推导出来
  }
  return dp[n];
};

鼓励我一下：

觉得还不错的话，给我的项目点个star吧