【代码随想录day22】斐波那契数

小小的香辛料

于 2023-08-16 23:11:22 发布

阅读量242

点赞数

分类专栏： LeetCode 数据结构文章标签：算法动态规划 leetcode python

本文链接：https://blog.csdn.net/doubleguy/article/details/132331039

版权

LeetCode 同时被 2 个专栏收录

112 篇文章

订阅专栏

数据结构

97 篇文章

订阅专栏

本文介绍了如何使用动态规划方法解决斐波那契数列问题，通过确定dp数组、初始化、递推公式和遍历顺序，展示了如何在Python中高效计算F(n)。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

斐波那契数 （通常用 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

思路

刷题时间不够了，秋招迫在眉睫，只能速成dp了。

今日通过最简单的题温习一下dp思想。

动态规划五步曲

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

class Solution:
    def fib(self, n: int) -> int:
        if n<2:
            return n
        # 1.确定dp以及下标含义（此处因为做了空间优化，就不涉及了）
        # 3.dp初始化
        f0 = 0
        f1 = 1
        res = 0
        # 4.确定遍历顺序
        for _ in range(n-1):
            # 2.确定递推公式
            res = f0+f1
            f0,f1 = f1,res
        return res