# Leetcode - 70 爬楼梯 js解法
### 题目
假设你正在爬楼梯。需要 *n* 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
**注意：** 给定 *n* 是一个正整数。
#### 示例一
```
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
```
#### 示例二
```
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
```
### 分析
> 只有两种方法爬楼梯：每次 <span style="color: #ff0000">1</span> 步和每次 <span style="color: #ff0000">2</span> 步。
>
> 假设有n个台阶，第一次可以是迈 <span style="color: #ff0000">1</span> 步或者迈 <span style="color: #ff0000">2</span> 步。
>
> 那么总方法数就是 <span style="color: #ff0000">第一次迈1步的所有方法</span> + <span style="color: #ff0000">第一次迈2步的所有方法</span> 。
>
> 迈了第一次，剩下的台阶数只可能是 <span style="color: #ff0000">n - 1</span> 或者 <span style="color: #ff0000">n - 2</span> 。
>
> 同理，<span style="color: #ff0000">n - 1</span> 或者 <span style="color: #ff0000">n - 2</span> 也可以分为第一次迈 <span style="color: #ff0000">1</span> 步和迈 <span style="color: #ff0000">2</span> 步 。
>
> 依此类推，实际上是一个<span style="color: #ff0000">斐波那契数列</span>。
## 代码
```javascript
/**
* @param {number} n
* @return {number}
*/
const fabonacci = n => {
if (n === 0) return 0
else if (n === 1) return 1
else if (n === 2) return 2
else return fabonacci(n - 1) + fabonacci(n - 2)
}
var climbStairs = function(n) {
return fabonacci(n)
}
```
- 这是首次尝试...自写一个斐波那契数列函数， 然后直接调用即可。
- 但提交结果为，<span style="color: #ff0000">超出时间限制</span> 。
##### 原因：
- 斐波那契数列函数中，存在大量的重复计算，比如算了fabonacci(n - 2)，那么下一次计算的fabonacci(n - 1) 也是一样的答案，这就造成了重复计算。
##### 解决方法：
- 利用<span style="color: #ff0000">缓存</span>把已经计算出的结果存起来。
### 改进代码
```javascript
/**
* @param {number} n
* @return {number}
*/
let cache = [0, 1, 2]
const fabonacci = n => {
return typeof cache[n] === 'number' ? cache[n] : cache[n] = fabonacci(n - 1) + fabonacci(n - 2)
}
var climbStairs = function(n) {
return fabonacci(n)
}
```
<span style="color: #ff0000">执行通过！</span>
> 执行用时 :60 ms, 在所有 javascript 提交中击败了82.73%的用户
> 内存消耗 :33.8 MB, 在所有 javascript 提交中击败了21.18%的用户
Leetcode - 70 爬楼梯 js解法
