leetcode 509题

leetcode 509 斐波那契数

斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例1

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例2

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

思路

思路一：带备忘录的递归

思路二：dp

思路三：使用 3 个指针来模拟 dp 过程

代码

// 思路一
var fib = function(n, memo = {}) {
    if (n <= 1) {
        return n;
    }

    if (memo[n]) {
        return memo[n];
    }

    return memo[n] = fib(n - 1) + fib(n - 2);
};

// 思路二
function fib(n) {
    const dp = [0, 1];

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

// 思路三
function fib(n) {
    if (n === 0) {
        return 0;
    }

    if (n <= 2) {
        return 1;
    }

    let prev1 = 1; // fib(1)
    let prev2 = 1; // fib(2)
    let sum = 0;

    for (let i = 3; i <= n; i++) {
        sum = prev1 + prev2;
        prev2 = prev1;
        prev1 = sum;
    }

    return sum;
}

复杂度分析:

时间复杂度: O(N)
空间复杂度：O(1)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python

leetcode 509 斐波那契数

思路

代码

CATALOG

FEATURED TAGS

FRIENDS