Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

爬楼梯 2 | 简单级-算法 #34

Open
OBKoro1 opened this issue Aug 1, 2019 · 0 comments
Open

爬楼梯 2 | 简单级-算法 #34

OBKoro1 opened this issue Aug 1, 2019 · 0 comments

Comments

@OBKoro1
Copy link
Owner

OBKoro1 commented Aug 1, 2019

博客链接

# 爬楼梯 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种方法

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

# 代码模板:

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

# 想一想再看答案

# 想一想再看答案

# 想一想再看答案

# 规律

除了前 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. 交换变量

实际上我们只需要 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. 数组形式:
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支持我一下~

博客链接

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant