爬楼梯
难度:简单
描述:
假设你正在爬楼梯,需要 n 步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?
样例:
比如 n=3,1+1+1=1+2=2+1=3,共有 3 种不同的方法
返回 3
思路分析:
这类题我们首先要来找其中的规律,找到了里面的规律,剩下的就好办了。
我再列举出几个结果:
1 | 0 =0 0种方法 |
想一下他们的规律,试着自己做出来。
代码模板:
1 | /** |
想一想再看答案
想一想再看答案
想一想再看答案
规律:
这道题的规律实际上跟之前做的查找斐波纳契数列中第 N 个数中的规律有点类似。
:::tip 斐波纳契数列中第 N 个数的规律
前 2 个数是 0 和 1,第 i 个数是第 i-1 个数和第 i-2 个数的和。
:::
本题中的规律是:
除了 1 阶楼梯和 2 阶楼梯是一种和两种方法之外,第 n 阶的楼梯的方法是第 i-1 阶楼梯和第 i-2 阶楼梯所用方法的和。
代码:
解题的核心就是逐步推导,推导出n前面的两个值。
- 数组:
1 | const climbStairs = function(n) { |
- 递归:
1 | const climbStairs = function(n) { |
- 交换变量:
实际上我们只需要 n 之前的两个值,就可以求出 n 所用的方法,所以我们没必要将 n 之前的所有值都推导出来。
所以我们只需要保存这两个值,然后再求出第三个值就可以了。
1 | const climbStairs = function(n) { |
实际上,我们也可以使用 ES6 的交换变量方法,而不用声明第三个变量:
1 | const climbStairs = function(n) { |
鼓励我一下:
觉得还不错的话,给我的点个star吧