关于动态规划:动态规划LeetCode-509斐波那契数列

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(斐波那契数列)