0509. 斐波那契数 #

• 标签：数组
• 难度：简单

题目大意 #

描述：给定一个整数 n。

要求：计算第 n 个斐波那契数。

说明：

• 斐波那契数列的定义如下：
  • f(0) = 0, f(1) = 1。
  • f(n) = f(n - 1) + f(n - 2)，其中 n > 1。

示例：

1
2
3

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

解题思路 #

思路 1：递归算法 #

根据我们的递推三步走策略，写出对应的递归代码。

1. 写出递推公式：f(n) = f(n - 1) + f(n - 2)。
2. 明确终止条件：f(0) = 0, f(1) = 1。
3. 翻译为递归代码：
   1. 定义递归函数：fib(self, n) 表示输入参数为问题的规模 n，返回结果为第 n 个斐波那契数。
   2. 书写递归主体：return self.fib(n - 1) + self.fib(n - 2)。
   3. 明确递归终止条件：
      1. if n == 0: return 0
      2. if n == 1: return 1

思路 1：递归算法代码 #

1
2
3
4
5
6
7

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        return self.fib(n - 1) + self.fib(n - 2)

思路 2：复杂度分析 #

• 时间复杂度：$O((\frac{1 + \sqrt{5}}{2})^n)$。具体证明方法参考 递归求斐波那契数列的时间复杂度，不要被网上的答案误导了 - 知乎。
• 空间复杂度：$O(n)$。每次递归的空间复杂度是 $O(1)$， 调用栈的深度为 $n$，所以总的空间复杂度就是 $O(n)$。

思路 2：动态规划算法 #

1. 划分阶段 #

我们可以按照整数顺序进行阶段划分，将其划分为整数 0 ~ n。

2. 定义状态 #

定义状态 dp[i] 为：第 i 个斐波那契数。

3. 状态转移方程 #

根据题目中所给的斐波那契数列的定义 f(n) = f(n - 1) + f(n - 2)，则直接得出状态转移方程为 dp[i] = dp[i - 1] + dp[i - 2]。

4. 初始条件 #

根据题目中所给的初始条件 f(0) = 0, f(1) = 1 确定动态规划的初始条件，即 dp[0] = 0, dp[1] = 1。

5. 最终结果 #

根据状态定义，最终结果为 dp[n]，即第 n 个斐波那契数为 dp[n]。

思路 2：动态规划代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n

        dp = [0 for _ in range(n + 1)]
        dp[0] = 0
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 2] + dp[i - 1]

        return dp[n]

思路 2：复杂度分析 #

• 时间复杂度：$O(n)$。一重循环遍历的时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$。用到了一维数组保存状态，所以总体空间复杂度为 $O(n)$。因为 dp[i] 的状态只依赖于 dp[i - 1] 和 dp[i - 2]，所以可以使用 3 个变量来分别表示 dp[i]、dp[i - 1]、dp[i - 2]，从而将空间复杂度优化到 $O(1)$。