0509. 斐波那契数 #
- 标签:数组
- 难度:简单
题目大意 #
描述:给定一个整数 $n$。
要求:计算第 $n$ 个斐波那契数。
说明:
- 斐波那契数列的定义如下:
- $f(0) = 0, f(1) = 1$。
- $f(n) = f(n - 1) + f(n - 2)$,其中 $n > 1$。
- $0 \le n \le 30$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:递归算法 #
根据我们的递推三步走策略,写出对应的递归代码。
- 写出递推公式:$f(n) = f(n - 1) + f(n - 2)$。
- 明确终止条件:$f(0) = 0, f(1) = 1$。
- 翻译为递归代码:
- 定义递归函数:
fib(self, n)
表示输入参数为问题的规模 $n$,返回结果为第 $n$ 个斐波那契数。 - 书写递归主体:
return self.fib(n - 1) + self.fib(n - 2)
。 - 明确递归终止条件:
if n == 0: return 0
if n == 1: return 1
- 定义递归函数:
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O((\frac{1 + \sqrt{5}}{2})^n)$。具体证明方法参考 递归求斐波那契数列的时间复杂度,不要被网上的答案误导了 - 知乎。
- 空间复杂度:$O(n)$。每次递归的空间复杂度是 $O(1)$, 调用栈的深度为 $n$,所以总的空间复杂度就是 $O(n)$。
思路 2:动态规划算法 #
1. 划分阶段 #
我们可以按照整数顺序进行阶段划分,将其划分为整数 $0 \sim 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:代码 #
|
|
思路 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)$。