爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?(给定 n 是一个正整数。)
思路分析:
这类题我们首先要来找其中的规律,找到了里面的规律,剩下的就好办了。
我再列举出几个结果:
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种方法
规律:
这道题的规律实际上跟之前做的查找斐波纳契数列中第 N 个数中的规律有点类似。
斐波纳契数列中第 N 个数的规律
前 2 个数是 0 和 1,第 i 个数是第 i-1 个数和第 i-2 个数的和。
本题中的规律是:
除了 1 阶楼梯和 2 阶楼梯是一种和两种方法之外,第 n 阶的楼梯的方法是第 i-1 阶楼梯和第 i-2 阶楼梯所用方法的和。
const climb = 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;
};
es6 解构赋值交换变量
const climb = 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;
}
最后更新于
这有帮助吗?