LeetCode 509(斐波那契数列)讲解

室长收录于找工作就像相亲和 LeetCode嘻唰唰

2023-03-15 约 300 字预计阅读 1 分钟

警告

本文最后更新于 2023-03-15，文中内容可能已过时。

Leetcode 509 题

抱歉拖更了 2 天，嘿嘿。这周我们基于动态规划基本思想，做一道 Leetcode 的简单题。

题干简述

Leetcode 509 题就是计算斐波那契数列。

公式：F(n) = F(n - 1) + F(n - 2)

给定：n

要求：计算F(n)

解题思路

为什么说计算斐波那契数列是动态规划里面最简单的一道题呢？

是因为题目直接给出了状态转移方程F(n) = F(n - 1) + F(n - 2)，拿着公式计算就可以了。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
          return 0

        dp = [0]*(n+1)
        dp[0] = 0
        dp[1] = 1

        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

复杂度

时间复杂度O(n)，空间复杂度O(n)。

转载声明：本文章允许转载，原文地址：「动态规划」LeetCode 509(斐波那契数列)

收录于合集・LeetCode嘻唰唰 7

LeetCode 1208(尽可能使字符串相等)讲解 LeetCode 70(爬楼梯)讲解

Buy me a coffee~

赞赏

支付宝

微信