题解 | #斐波那契数列#

方法一：递归（我的第一想法）

如何计算递归的时间复杂度？

首先计算子问题个数：递归中的子问题个数即为递归树中节点的总数。二叉树的节点总数为指数级别，所以子问题个数为O(2ⁿ)
然后计算解决一个子问题的时间：在本算法中没有循环，只有一个加法操作，所以时间为O(1)
综上，这个算法的时间复杂度为二者相乘，为O(2ⁿ)

递归算法的缺点

这个算法的递归树存在大量的重复节点（比如两个f(18)节点），即会进行大量的重复计算，增加了运算时间。
重叠子问题就体现为递归树中有大量重复节点，可以考虑用动态规划方法解决。

递归解法的时间和空间复杂度

时间复杂度：O(2ⁿ)
空间复杂度：递归栈的空间

/*
 * @Author: LibraStalker **********
 * @Date: 2023-03-25 16:19:58
 * @FilePath: BM62-斐波那契数列.js
 * @Description:
 */
function Fibonacci(n) {
    // write code here
    if (n === 1 || n === 2) {
        return 1;
    }

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
module.exports = {
    Fibonacci: Fibonacci,
};

方法二：记忆化搜索（带备忘录的递归解法）

带备忘录的递归解法的优点

直接递归会存在许多重复计算，一般使用map或者array等数据结构充当备忘录，保存子问题的结果，后续如果有重复子问题可以直接拿备忘录中的结果，避免了重复计算。
带备忘录的递归算法，把一棵存在巨量冗余的递归树通过剪枝，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

带备忘录的递归解法和迭代的动态规划解法的区别

带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和常见的动态规划解法已经差不多了，但是带备忘录的递归解法增加了备忘录，会增加空间复杂度。
带备忘录的递归解法是自顶向下进行递归求解，我们更常见的动态规划代码是自底向上进行递推求解。

自顶向上递归解法和自底向下递推解法

自顶向上递归解法从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫自顶向下。
自底向下递推解法从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到我们想要的答案 f(20)。这就是递推的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因。

带备忘录的递归解法的时间和空间复杂度

时间复杂度：O(n)（因为没有重复的节点，子问题的个数就是输入规模n，所以子问题个数为O(n)，子问题规模还是O(1)，两者相乘得到O(n)）
空间复杂度：O(n)和递归栈的空间

/*
 * @Author: LibraStalker **********
 * @Date: 2023-03-25 16:19:58
 * @FilePath: BM62-斐波那契数列.js
 * @Description:
 */
const result = new Array(50).fill(0);
function Fibonacci(n) {
    // write code here
    if (n === 1 || n === 2) {
        result[n] = 1;
        return result[n];
    }

    if (result[n] > 0) {
        return result[n];
    }

    result[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
    return result[n];
}
module.exports = {
    Fibonacci: Fibonacci,
};

方法三：动态规划-DP数组

DP数组和备忘录的关系

DP数组和带备忘录的递归解法中的备忘录类似，就是记录了各个子问题的结果。带备忘录的递归解法中的备忘录，最终完成后就是这个DP数组。
DP数组的动态规划解法的效率和带备忘录的递归解法效率基本相同。

状态转移方程

状态转移方程实际上就是描述问题结构的数学形式，是解决问题的核心，其实状态转移方程直接代表着暴力解法。
f(n) 的函数参数会不断变化，所以你把参数 n 想做一个状态，这个状态 n 是由状态 n - 1 和状态 n - 2 转移（相加）而来，这就叫状态转移。
带备忘录的递归解法和动态规划的DP数组解法都是围绕这个方程式的不同表现形式。

动态规划的DP数组解法的时间和空间复杂度

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

/*
 * @Author: LibraStalker **********
 * @Date: 2023-03-25 16:19:58
 * @FilePath: BM62-斐波那契数列.js
 * @Description:
 */

function Fibonacci(n) {
    const dpResult = new Array(41).fill(0);
    dpResult[1] = 1;
    dpResult[2] = 1;

    for (let i = 3; i <= n; ++i) {
        dpResult[i] = dpResult[i - 1] + dpResult[i - 2];
    }
    return dpResult[n];
}
module.exports = {
    Fibonacci: Fibonacci,
};

方法四：动态规划-缩减DP数组

DP数组的优化

动态规划的DP数组中保存着所有状态的结果，但是有时状态转移只需要DP数组中的一部分状态，则可以缩小DP数组的大小，只记录必要的数据，从而降低空间复杂度。
斐波那契数列问题中当前状态只和之前的两个状态有关，因此不需要那么长的DP数组存储所有状态，只要想办法存储之前的两个状态就行了。

动态规划问题的三个特征

重复子问题：重复子问题可以从递归树中的重复节点体现出来，斐波那契数列问题旨在说明重叠子问题的消除方法，演示得到最优解法逐步求精的过程。
无后效性：当前状态不会受到后面状态的影响，只跟前面的状态有关。
最优子结构：后面的状态可以通过前面的状态推导出来。

动态规划的缩减DP数组解法的时间和空间复杂度

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

/*
 * @Author: LibraStalker **********
 * @Date: 2023-03-25 16:19:58
 * @FilePath: BM62-斐波那契数列.js
 * @Description:
 */

function Fibonacci(n) {
    if (n === 1 || n === 2) {
        return 1;
    }

    let dp_i_1 = 1;
    let dp_i_2 = 1;
    let dp_i;

    for (let i = 3; i <= n; ++i) {
        dp_i = dp_i_1 + dp_i_2;
        dp_i_1 = dp_i_2;
        dp_i_2 = dp_i;
    }
    return dp_i;
}
module.exports = {
    Fibonacci: Fibonacci,
};