# 爬楼梯 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种方法
1
2
3
4
5
2
3
4
5
查找样例中的规律：爬楼梯
# 代码模板：
/**
* @param n: An integer
* @return: An integer
*/
const climbStairs2 = function(n) {}
1
2
3
4
5
2
3
4
5
# 想一想再看答案
# 想一想再看答案
# 想一想再看答案
# 规律
除了前 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))
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
- 交换变量
实际上我们只需要 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
2
3
4
5
6
7
8
9
10
11
- 数组形式：
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
2
3
4
5
6
7
8