爬楼梯 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种方法
51 * 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种方法
1
2
3
4
5

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

代码模板:

/**
 * @param n: An integer
 * @return: An integer
 */
const climbStairs2 = function(n) {};
1
2
3
4
5

想一想再看答案

想一想再看答案

想一想再看答案

规律

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

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

代码:

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

  1. 递归

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

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));
1
2
3
4
5
6
7
8
9
10
11
  1. 交换变量

实际上我们只需要 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));
1
2
3
4
5
6
7
8
9
10
11
  1. 数组形式:
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];
};
1
2
3
4
5
6
7
8

鼓励我一下:

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

Last Updated: 11/4/2018, 3:47:41 PM