算法_爬楼梯

OBKoro1

发布于 2020-10-27 11:55:12

3280

发布于 2020-10-27 11:55:12

文章被收录于专栏：OBKoro1的前端分享

爬楼梯

难度：简单

描述：

假设你正在爬楼梯，需要 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种方法

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

代码模板：

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

想一想再看答案

规律：

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

:::tip 斐波纳契数列中第 N 个数的规律前 2 个数是 0 和 1,第 i 个数是第 i-1 个数和第 i-2 个数的和。 :::

本题中的规律是：

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

代码：

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

数组：

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));

递归：

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));

交换变量：

实际上我们只需要 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));

实际上，我们也可以使用 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));

鼓励我一下：

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2018-10-12，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 OBKoro1前端进阶积累微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度