华为 OD 训练营 · 题解精讲
LC509. 斐波那契数
LC509. 斐波那契数
题目描述
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。 示例 1： 输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1 示例 2： 输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2 示例 3： 输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3 提示： 0 <= n <= 30
题目解析
解题思路
本题是经典的斐波那契数列计算，参考代码给出了三种实现方式：纯递归、记忆化搜索和动态规划。题目要求计算 F(n)，核心是利用递推关系 F(n) = F(n-1) + F(n-2)。
- 纯递归：直接按定义递归，但存在大量重复计算，时间复杂度为指数级。
- 记忆化搜索：在递归基础上引入
memo数组缓存已计算过的子问题结果，避免重复递归，将复杂度降为 O(n)。 - 动态规划：自底向上迭代，用
dp数组记录每一步结果，无需递归调用，效率最高。
参考代码中实际执行的是动态规划版本（myFib3），它用一个长度为 N+1 的数组 dp 存储从 0 到 N 的所有斐波那契数，然后通过循环依次计算。
关键步骤
1. 边界处理：若 N < 2，直接返回 N（即 F(0)=0, F(1)=1）。 2. 初始化 dp 数组：dp[0] = 0，dp[1] = 1。 3. 迭代计算：从 i = 2 到 N，执行 dp[i] = dp[i-1] + dp[i-2]。 4. 返回结果：dp[N] 即为所求。
迭代过程示意（以 N=4 为例）：
dp[0]=0, dp[1]=1
i=2: dp[2] = dp[1]+dp[0] = 1+0 = 1
i=3: dp[3] = dp[2]+dp[1] = 1+1 = 2
i=4: dp[4] = dp[3]+dp[2] = 2+1 = 3复杂度分析
- 时间复杂度：O(n)，只需一次循环计算 n-1 次加法。
- 空间复杂度：O(n)，用于存储长度为 n+1 的 dp 数组。若进一步优化，可只用两个变量滚动更新，将空间降至 O(1)，但参考代码未采用此优化。
参考代码
class Solution:
def __init__(self):
self.times1 = 0
def fib(self, N):
self.times1 = 0
result = self.myFib1(N)
print(self.times1)
return result
def myFib1(self, N):
self.times1 += 1
if N == 0:
return 0
if N == 1:
return 1
return self.myFib1(N - 1) + self.myFib1(N - 2)
# 记忆化搜索
class Solution:
def __init__(self):
self.times1 = 0
self.memo = None
def fib(self, N):
self.times1 = 0
self.memo = [-1] * (N + 1)
result = self.myFib2(N)
print("myFib2 调用的次数为: ", self.times1)
return result
def myFib2(self, N):
self.times1 += 1
if N == 0:
return 0
if N == 1:
return 1
if self.memo[N] == -1:
self.memo[N] = self.myFib2(N - 1) + self.myFib2(N - 2)
return self.memo[N]
# 动态规划
class Solution:
def __init__(self):
self.times1 = 0
self.memo = None
def fib(self, N):
self.times1 = 0
self.memo = [-1] * (N + 1)
result = self.myFib3(N)
print("myFib3 调用的次数为: ", self.times1)
return result
def myFib3(self, N):
if N < 2:
return N
dp = [-1] * (N + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, N + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[N]