当前位置：首页 > news >正文

LeetCode_LCR 509 斐波拉契

news 2025/6/6 9:56:28

斐波那契数：从递归到动态规划的优化之旅

问题描述

斐波那契数列以 F(0) = 0 和 F(1) = 1 开始，后续每一项都是前两项之和。给定整数 n，要求计算 F(n)。

示例：

n = 2 → 输出 1（F(2) = F(1) + F(0) = 1 + 0）
n = 3 → 输出 2（F(3) = F(2) + F(1) = 1 + 1）
n = 4 → 输出 3（F(4) = F(3) + F(2) = 2 + 1）

约束：0 ≤ n ≤ 30

解法分析

斐波那契数列是经典的递归问题，但直接递归会导致大量重复计算。以下是逐步优化的解法：

1. 递归解法（不推荐）

直接递归是最直观的解法，但时间复杂度为指数级（ $O(2^n)$ ），在 n 较大时效率极低。

public int fib(int n) {if (n == 0) return 0;if (n == 1) return 1;return fib(n - 1) + fib(n - 2);
}

2. 记忆化搜索（自顶向下）

通过缓存已计算结果避免重复计算，时间复杂度优化为 $O (n)$ ，空间复杂度为 $O (n)$ （递归栈空间 + 缓存数组）。

代码实现：

class Solution {int[] arr = new int[31]; // 缓存数组，n最大为30public int fib(int n) {return f(n);}private int f(int n) {if (n == 0) return 0;if (n == 1) return 1;if (arr[n] != 0) return arr[n]; // 命中缓存arr[n] = f(n - 1) + f(n - 2); // 计算并缓存return arr[n];}
}

关键点：

初始化缓存数组：大小为 31（n 最大为 30）。
递归终止条件：n = 0 或 n = 1 时直接返回。
缓存查询：优先检查缓存，避免重复计算。

3. 动态规划（自底向上）

迭代代替递归，消除递归栈开销。时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ （仅需缓存数组）。

代码实现：

class Solution {public int fib(int n) {if (n <= 1) 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];}
}

4. 空间优化动态规划

只保留最近两个状态，空间复杂度优化至 $O (1)$ 。

class Solution {public int fib(int n) {if (n <= 1) return n;int a = 0, b = 1;for (int i = 2; i <= n; i++) {int c = a + b;a = b;b = c;}return b;}
}

总结

方法	时间复杂度	空间复杂度	适用场景
直接递归	$O(2^n)$	$O (n)$	仅限极小的 `n`
记忆化搜索	$O (n)$	$O (n)$	通用，但递归有栈开销
动态规划	$O (n)$	$O (n)$	无栈溢出风险
优化动态规划	$O (n)$	$O (1)$	最优解，推荐使用