如何在 Python 中实现斐波那契数列的动态规划版本？

  • mingtian66

    2024-11-12 16:03:19
  • Python
  • 原创

在 Python 中，可以用动态规划实现斐波那契数列。动态规划的思想是通过保存之前计算的结果，避免重复计算，提升效率。斐波那契数列的递推关系是：
F(n)=F(n−1)+F(n−2)
F(n)=F(n−1)+F(n−2)

对于第 00 项和第 11 项的初始值分别为 F(0)=0F(0)=0 和 F(1)=1F(1)=1。

以下是实现代码：

def fibonacci(n):
    if n <= 1:
        return n

    # 创建一个数组来存储斐波那契数列的计算结果
    fib = [0] * (n + 1)
    fib[0], fib[1] = 0, 1

    # 使用循环填充数组
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]

    return fib[n]

示例用法

print(fibonacci(10))  # 输出：55

代码说明

    如果 n 小于等于 1，直接返回 n，因为 F(0) = 0 和 F(1) = 1。
    初始化一个数组 fib 用于存储计算结果，避免重复计算。
    使用 for 循环依次计算 fib[i]，从 2 到 n，每次都根据 fib[i - 1] 和 fib[i - 2] 的值来计算 fib[i]。
    最后返回 fib[n]。

优化空间复杂度的版本

只保存最近的两个值，可以将空间复杂度从 O(n)O(n) 降到 O(1)O(1)：

def fibonacci(n):
    if n <= 1:
        return n

    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b

    return b

这个优化版本的逻辑是使用两个变量 a 和 b 来追踪最近的两个斐波那契数，依次迭代计算。

请使用浏览器的分享功能分享到微信等