玉林网站设计,供求信息网站开发背景,海淀区玉泉小学网站 建设方,网站搭建配置题目#xff1a;509. 斐波那契数
难度#xff1a;简单
斐波那契数 #xff08;通常用 F(n) 表示#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a;
F(0) 0#xff0c;F(1) 1
F(n…题目509. 斐波那契数
难度简单
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(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示例 3
输入n 4
输出3
解释F(4) F(3) F(2) 2 1 3提示
0 n 30
一、模式识别动态规划
递推公式直接都给你了。。。
五部曲
1.动规数组意义题目本身
2.递推公式直接就有
3.初始化这里有个重要的点
4.遍历顺序本题常规根据递推公式可知是从前往后
5.举例较简单这里省略
二、代码实现
这几种实现方式背后的代码逻辑相同但各有优劣
1.缓存从0到n的F
该方法可读性较强耗时低但占空间较高
class Solution:def fib(self, n: int) - int:if n 1:return ndp [0] * (n 1)dp[1] 1for i in range(2, n 1):dp[i] dp[i - 1] dp[i - 2]return dp[n]
时间复杂度O(n)空间复杂度O(n)
耗时0ms
2.只缓存两个F
该方法可读性较弱但耗时和占空间都较低
class Solution:def fib(self, n: int) - int:if n 1:return ndp [0, 1]for i in range(2, n 1):res dp[0] dp[1]dp[0], dp[1] dp[1], resreturn dp[1]
时间复杂度O(n)空间复杂度O(1)
耗时0ms
3.递归
该方法可读性较弱但耗时较高
class Solution:def fib(self, n: int) - int:if n 1:return nreturn self.fib(n - 1) self.fib(n - 2)
时间复杂度O(n)空间复杂度O(1)
耗时20ms
三、TIP
本题需要注意初始化不然就会写出这样的代码
class Solution:def fib(self, n: int) - int:dp [0] * (n 1)dp[1] 1for i in range(2, n 1):dp[i] dp[i - 1] dp[i - 2]return dp[n]
然后就会这样
IndexError: list assignment index out of range ~~^^^ dp[1] 1 Line 4 in fib (Solution.py) ^^^^^^^^^^^^^^^^^^^^^^^ ret Solution().fib(param_1) Line 32 in _driver (Solution.py) _driver() Line 47 in module (Solution.py)
最后执行的输入
n
0
