斐波那契数 (opens new window)

• 难度：Easy
• 标签：递归 记忆化递归 递推 动态规划 黄金分割比

刷题思路

• [x] 记忆化递归
• [x] 递推(DP)
• [x] DP 优化
• [x] 黄金分割比公式

方法 1 记忆化递归

• 复杂度：
  • 时间 O(N). 通过记忆化去除冗余计算故每个项只需计算一次.
  • 空间 O(N). 递归调用栈深度与 N 一致 & 使用长度为 N 的数组实现记忆化.
• 结果:
  • 执行用时：80 ms, 在所有 JavaScript 提交中击败了71.32%的用户
  • 内存消耗：37.4 MB, 在所有 JavaScript 提交中击败了7.79%的用户

var fib = function(N) {
    const arr = [0, 1]
    return recursion(N, arr)
};

function recursion (N, arr) {
    if (arr[N] != null) return arr[N]
    arr[N-2] = recursion(N-2, arr)
    arr[N-1] = recursion(N-1, arr)
    return arr[N-2] + arr[N-1]
}

方法 2 递推(DP)

• 复杂度：
  • 时间 O(N). 一轮遍历.
  • 空间 O(N). 使用长度为 N 的数组实现记忆化.
• 结果:
  • 执行用时：84 ms, 在所有 JavaScript 提交中击败了58.39%的用户
  • 内存消耗：37.4 MB, 在所有 JavaScript 提交中击败了7.40%的用户

var fib = function(N) {
    const dp = [0, 1]
    for (let i=2; i<=N; i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[N]
};

方法 3 DP 优化

• 复杂度：
  • 时间 O(N). 一轮遍历.
  • 空间 O(1). 常量级额外空间.
• 结果:
  • 执行用时：84 ms, 在所有 JavaScript 提交中击败了58.39%的用户
  • 内存消耗：37.3 MB, 在所有 JavaScript 提交中击败了9.67%的用户

var fib = function(N) {
    if (N < 2) return N
    let [a, b] = [0, 1]
    for (let i=2; i<=N; i++) {
        [a, b] = [b, a+b]
    }
    return b
};

方法 4 黄金分割比公式

• 复杂度：
  • 时间 O(1).
  • 空间 O(1).
• 结果:
  • 执行用时：80 ms, 在所有 JavaScript 提交中击败了71.32%的用户
  • 内存消耗：37.2 MB, 在所有 JavaScript 提交中击败了13.99%的用户

var fib = function(N) {
    const ratio = (1 + Math.sqrt(5)) / 2
    return Math.round(Math.pow(ratio, N) / Math.sqrt(5))
};

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~