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 阶

分析

只有两种方法爬楼梯：每次 1 步和每次 2 步。

假设有n个台阶，第一次可以是迈 1 步或者迈 2 步。

那么总方法数就是 第一次迈1步的所有方法 + 第一次迈2步的所有方法 。

迈了第一次，剩下的台阶数只可能是 n - 1 或者 n - 2 。

同理，n - 1 或者 n - 2 也可以分为第一次迈 1 步和迈 2 步 。

依此类推，实际上是一个斐波那契数列。

代码

/**
 * @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)
}

• 这是首次尝试...自写一个斐波那契数列函数， 然后直接调用即可。
• 但提交结果为，超出时间限制 。

原因：

• 斐波那契数列函数中，存在大量的重复计算，比如算了fabonacci(n - 2)，那么下一次计算的fabonacci(n - 1) 也是一样的答案，这就造成了重复计算。

解决方法：

• 利用缓存把已经计算出的结果存起来。

改进代码

/**
 * @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)
}

执行通过！

执行用时 :60 ms, 在所有 javascript 提交中击败了82.73%的用户
内存消耗 :33.8 MB, 在所有 javascript 提交中击败了21.18%的用户