2021-01-04 | 509. 斐波那契数

小鱼儿 2023-01-02 05:25 176阅读 0赞

### 1. 题目描述 ###

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

F(0) = 0,   F(1) = 1
    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N，计算 F(N)。  
示例 1：

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

示例 2：

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

示例 3：

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

### 2. 解题思路 ###

**（1）暴力递归：** 最简单的方式就是递归，根据题目中给出的斐波那契数列公式进行递归遍历。这种方式存在重复调用计算的问题。

*  **时间复杂度：O(n2)**
 *  **空间复杂度：O(1)**

**（2）递归 + 缓存：** 由于递归在遍历的过程中，存在很多节点重复计算的情况，所以我们可以将每次求的值进行缓存，以便于后面计算时使用。这里我们**使用闭包来缓存**每次计算的值。

*  **时间复杂度：O(n)**
 *  **空间复杂度：O(1)**

**（3）动态规划：** 这里使用了动态规划，本质上也是在对已经计算好的结果进行缓存，只不过不用递归了，而是显式的进行迭代。

*  **时间复杂度：O(n)**
 *  **空间复杂度：O(1)**

**（4）动态规划：** 这里使用了动态规划，我们发现每次计算`fib(N)`，只需要用到`fib(N-1)`和`fib(N-2)`，所以只需要使用两个变量来缓存就好了。

*  **时间复杂度：O(n)**
 *  **空间复杂度：O(1)**

### 3. 代码实现 ###

**（1）暴力递归**

/** * @param {number} N * @return {number} */
    var fib = function(N) { 
        if (N < 1) return 0
        if (N === 1 || N === 2) return 1;
        return fib(N - 1) + fib(N - 2);
    };

**（2）递归 + 缓存**

**（3）动态规划**

/** * @param {number} N * @return {number} */
    var fib = function(N) { 
        if (N < 1) return 0
        if (N === 1 || N === 2) return 1;
        let pre = 1, cur = 1, sum = 0; // pre前一位数字的累加和, cur当前数字, sum当前数字的累加和
        for (let i = 3; i <= N; i++) { 
            sum = pre + cur;
            pre = cur;
            cur = sum;
        }
        return cur;
    };

**（4）动态规划**

/** * @param {number} N * @return {number} */
    var fib = function(N) { 
       if (N < 1) return 0
       if (N === 1 || N === 2) return 1;
       const res = [0,1]
       for(let i= 2; i <= N; i++){ 
          res[i] = res[i-1] + res[i-2]
       }
       return res[N]
    };

### 4. 提交结果 ###

**（1）暴力递归**  
![在这里插入图片描述][20210104222916380.png]

**（2）递归 + 缓存**  
![在这里插入图片描述][20210104222933430.png]

**（3）动态规划**  
![在这里插入图片描述][20210104222949939.png]

**（4）动态规划**  
![在这里插入图片描述][20210104223003997.png]

[20210104222916380.png]: /images/20221120/27169e11798e4f5faf208620ca09ea77.png?
[20210104222933430.png]: /images/20221120/35e3c1e58a4046d683875464488197cb.png?
[20210104222949939.png]: /images/20221120/ea7d4be5bf2b4f41893ffcd01e735f58.png?
[20210104223003997.png]: /images/20221120/79415ad732c44693922ee15018b87db7.png?