斐波拉契函数的解决方案

斐波那契数列Fibonacci sequence的定义很简单前两项是 0 和 1之后每一项都是前两项之和F(0)0, F(1)1, F(n)F(n-1)F(n-2)。根据你对时间复杂度和空间复杂度的不同需求通常有以下几种主流的解决方案1. 基础递归不推荐用于大数最直观的写法但存在大量重复计算。def fib_recursive(n): if n 1: return n return fib_recursive(n - 1) fib_recursive(n - 2)2. 记忆化搜索 / 动态规划自顶向下 / 自底向上通过缓存已计算的结果来避免重复工作。​​​​​​​# 自底向上迭代推荐 def fib_dp(n): if n 1: return n dp [0] * (n 1) dp[1] 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]3. 空间优化的迭代 最佳工程实践因为只需要前两个状态所以不需要整个数组。​​​​​​​def fib_optimized(n): if n 1: return n a, b 0, 1 for _ in range(2, n 1): a, b b, a b # Python 特有的并行赋值无需临时变量 return b4. 矩阵快速幂适用于超大 $n$​​​​​​​def multiply(A, B): return [ [A[0][0]*B[0][0] A[0][1]*B[1][0], A[0][0]*B[0][1] A[0][1]*B[1][1]], [A[1][0]*B[0][0] A[1][1]*B[1][0], A[1][0]*B[0][1] A[1][1]*B[1][1]] ] def matrix_pow(M, n): result [[1, 0], [0, 1]] # 单位矩阵 base M while n 0: if n % 2 1: result multiply(result, base) base multiply(base, base) n // 2 return result def fib_matrix(n): if n 1: return n M [[1, 1], [1, 0]] result matrix_pow(M, n - 1) return result[0][0]5. 通项公式数学解法​​​​​​​ 总结对比方案时间复杂度空间复杂度适用场景普通递归仅用于教学严禁生产环境DP / 记忆化需要保留中间结果时滚动变量99% 的面试/工程场景矩阵快速幂 建议如果是LeetCode/面试直接写方案3滚动变量。如果是Python 简单脚本直接用functools.lru_cache装饰器实现记忆化递归最省事。你需要针对特定语言如 Java/C/Go的实现或者需要处理大数取模如 $10^97$的代码吗