共计 392 个字符,预计需要花费 1 分钟才能阅读完成。
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)
,拿着公式计算就能够了。
代码实现
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(斐波那契数列)
正文完