# 爬楼梯
# 难度：简单
# 描述：
假设你正在爬楼梯，需要 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
2
3
4
5
6
想一下他们的规律，试着自己做出来。
# 代码模板：
/**
* @param n: An integer
* @return: An integer
*/
const climbStairs = function(n) {};
1
2
3
4
5
2
3
4
5
# 想一想再看答案
# 想一想再看答案
# 想一想再看答案
# 规律：
这道题的规律实际上跟之前做的查找斐波纳契数列中第 N 个数中的规律有点类似。
斐波纳契数列中第 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));
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
- 递归：
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
2
3
4
5
6
7
8
9
10
- 交换变量：
实际上我们只需要 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
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
2
3
4
5
6
7
8
9
10
11
12