算法-爬楼梯 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吧
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2018-11-08，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 OBKoro1前端进阶积累 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
