ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > Python > 如何在 Python 中实现斐波那契数列的动态规划版本？

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

原创 Python 作者：mingtian66 时间：2024-11-12 16:03:19 0 删除 编辑

在 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 来追踪最近的两个斐波那契数，依次迭代计算。

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70040412/viewspace-3048500/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： Throwable 和 Exception 的区别是什么？
下一篇： 如何在 Python 中使用递归反转链表？
请登录后发表评论 登录
全部评论
mingtian66

注册时间：2024-08-07

  • 博文量
    589
  • 访问量
    602978

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593