FatGod Blog
搜索 K

Appearance

🔗 斐波那契数 ​

📝 题目描述 ​

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

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

斐波那契数列

​ 现给定n，请你计算出F(n)。

📋 代码模版 ​

java
class Solution {
    public int fib(int n) {

    }
}
typescript
function fib(n: number): number {

}

💡 提示 ​

  1. 0≤n≤30

🚀 示例 ​

示例

🖊️ 题解 ​

记忆化搜索 ​

​ 本题直接给出了⭐️斐波那契数列中第i（1 < i <= n）个数字值⭐️的方程式f(i)=f(i−1)+f(i−2)，因此该题最简单的解决方案就是深度优先搜索dfs，递归公式为dfs(i)=dfs(i−1)+dfs(i−2)。同时，题目描述中也直接给出了递归边界，为 dfs(0)=0,dfs(1)=1。

​ 综上所述，我们很容易写出以下代码。

java
class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
}
typescript
function fib(n: number): number {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

​ 😭但经过实践，这种算法的效率并不是很高。

运行效率低

​ 那么，导致以上代码运行效率低下的原因是什么呢？接下来，让我们来分析一下它的时间复杂度。假设n = 5，可以画出以下递归树。

递归树

​ 递归树为一颗二叉树。其中，每个节点都代表一个子问题的计算，节点总数为指数级别。因此，我们可以得出结论：随着n的增大，由于重复计算不断增加，子问题的个数也随之呈指数级增长。基于此，这个算法的时间复杂度为O(2n)。

​ ⭐以上所述为多路递归的典型问题，即重复计算。为了应对这个问题，经典的解决方法是创建一个「备忘录」，在计算每个子问题之前先查找备忘录。如果备忘录中没有记录计算结果，就进行计算并将结果记录在备忘录中；反之，则直接获取记录的值并返回。

tip: 多路递归是指递归函数体中多次调用了自身。

​ 这种带备忘录的递归算法通常也被称为记忆化搜索，对应本题的算法代码如下。

java
class Solution {
    public int fib(int n) {
        int[] memory = new int[n + 1];
        return dfs(n, memory);
    }

    private int dfs(int i, int[] memory) {
        if (i <= 1) {
            return i;
        }
        if (memory[i] != 0) {
            return memory[i];
        }
        return memory[i] = dfs(i - 1, memory) + dfs(i - 2, memory);
    }
}
typescript
function fib(n: number): number {
    const memory: number[] = [];
    const dfs = (i: number): number => {
        if (i <= 1) {
            return i;
        }
        if (memory[i] !== undefined) {
            return memory[i];
        }
        return memory[i] = dfs(i - 1) + dfs(i - 2);
    }
    return dfs(n);
}

​ 记忆化搜索是一种典型的空间换时间的思想，它是在一颗存在大量冗余的递归树上通过「剪枝」，保证了每个相同的节点只计算一次。因此，该算法的时间复杂度为 O(n)，空间复杂度为 O(n)。

记忆化搜索树

动态规划 ​

​ 根据以上dfs的解法，我们可以很轻松地将其翻译成动态规划dp解法，具体步骤如下。

  1. 状态定义：设 dp 为一维数组，其中 dp[i] 代表⭐️斐波那契数列中第i个数字的值⭐️。
  2. 初始状态：根据边界条件，初始化 dp 数组的前两项，即 $dp[0] = 0, dp[1] = 1 $。
  3. 状态转移方程：dp[i]=dp[i−1]+dp[i−2]，其中 $ 2 \leq i \leq n$。
  4. 返回值：dp[n]​，即F(n)的值。
java
class Solution {
    public int fib(int n) {
        if (n <= 0) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
typescript
function fib(n: number): number {
    if (n <= 0) {
        return n;
    }
    const dp: number[] = [];
    dp[0] = 0;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

​ 以上算法需要一个很长的DP table（ dp 数组）来存储所有的状态，但我们仔细观察状态转移方程 dp[i]=dp[i−1]+dp[i−2]，可以发现当前状态的计算只依赖于前两个状态。因此我们可以通过「滚动数组」的思想，利用若干变量替代 dp 数组，在保持算法的时间复杂度不变的前提下，将空间复杂度从 O(n)优化至 O(1)​​。

​ 这种技巧通常也被称为状态压缩，对应本题的算法代码如下。

java
class Solution {
    public int fib(int n) {
        if (n <= 0) {
            return n;
        }
        int pre = 0, cur = 1;
        for (int i = 2; i <= n; i++) {
            int sum = pre + cur;
            pre = cur;
            cur = sum;
        }
        return cur;
    }
}
typescript
function fib(n: number): number {
    if (n <= 0) {
        return n;
    }
    let pre = 0, cur = 1;
    for (let i = 2; i <= n; i++) {
        const sum = pre + cur;
        pre = cur;
        cur = sum;
    }
    return cur;
}

💭 复杂度分析 ​

​ 基于记忆化搜索的解决方案的复杂度分析如下。

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

​ 基于动态规划的最优（状态压缩）解决方案的复杂度分析如下。

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

上次更新于: