爬楼梯

难度:简单

描述:

假设你正在爬楼梯,需要 n 步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

样例:

比如 n=3,1+1+1=1+2=2+1=3,共有 3 种不同的方法

返回 3

思路分析:

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

我再列举出几个结果:

0 =0 0种方法
1 = 1 种方法
2 = 1+1 =2 2种方法
3=1+1+1=1+2=2+1 3种方法
4 = 1*4 = 1+2+1 = 1+1+2 = 2+1+1 = 2+2 5种方法
5 = 1*5 = 2+1+2 =2+2+1 = 1+2+2 =1+2+1+1 = 1+1+2+1 = 2+1+1+1 = 1+1+1+2 8种方法
1
2
3
4
5
6

想一下他们的规律,试着自己做出来。

代码模板:

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

想一想再看答案

想一想再看答案

想一想再看答案

规律:

这道题的规律实际上跟之前做的查找斐波纳契数列中第 N 个数中的规律有点类似。

斐波纳契数列中第 N 个数的规律

前 2 个数是 0 和 1,第 i 个数是第 i-1 个数和第 i-2 个数的和。

本题中的规律是

除了 1 阶楼梯和 2 阶楼梯是一种和两种方法之外,第 n 阶的楼梯的方法是第 i-1 阶楼梯和第 i-2 阶楼梯所用方法的和。

代码:

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

  1. 数组:
const climbStairs = function(n) {
  let dp = [0, 1, 2]; // 初始数组 前面三个没有规律
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]; // 从3开始都是可以由前面两个元素相加推导出来
  }
  return dp[n];
};
console.log(climbStairs(3), climbStairs(4), climbStairs(5));
1
2
3
4
5
6
7
8
  1. 递归:
const climbStairs = function(n) {
  function item(n) {
    // 循环退出条件
    if (n === 1) return 1;
    if (n === 2) return 2;
    return item(n - 1) + item(n - 2); // 将递归到1个楼梯和两个楼梯 最后反推到n个楼梯
  }
  return item(n);
};
console.log(climbStairs(3), climbStairs(4), climbStairs(5));
1
2
3
4
5
6
7
8
9
10
  1. 交换变量:

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

所以我们只需要保存这两个值,然后再求出第三个值就可以了。

const climbStairs = function(n) {
  // 前两个值的返回结果
  if (n === 1) return 1;
  if (n === 2) return 2;
  let a = 1, // 1阶楼梯
    b = 2, // 2阶楼梯
    c;
  for (let i = 3; i <= n; i++) {
    c = a + b; // n的结果
    // 为了后续推导,不断保存前两个值
    a = b;
    b = c;
  }
  return c;
};
console.log(climbStairs(3), climbStairs(4), climbStairs(5));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

实际上,我们也可以使用 ES6 的交换变量方法,而不用声明第三个变量:

const climbStairs = function(n) {
  // 前两个值的返回结果
  if (n === 1) return 1;
  if (n === 2) return 2;
  let a = 1,
    b = 2;
  for (var i = 3; i <= n; i++) {
    [a, b] = [b, b + a];
  }
  return b;
};
console.log(climbStairs(3), climbStairs(4), climbStairs(5));
1
2
3
4
5
6
7
8
9
10
11
12

鼓励我一下:

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

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