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%的用户


A new frontend developer.