潍坊高级网站建设推广,wordpress仿36kr主题,南宁门户网站有哪些,南宁网约车资格证网上报名题目#xff1a;
斐波那契数 #xff08;通常用 F(n) 表示#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a;
F(0) 0#xff0c;F(1) 1 F(n) F(n - 1) F(n - 2)#xff0c;其中…题目
斐波那契数 通常用 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
思路
本题很简单但很适合用来做动态规划和递归的入门题本篇文章主要讲解一下动态规划的思路。
动态规划
动规五部曲
这里我们要用一个一维dp数组来保存递归的结果
确定dp数组以及下标的含义
dp[i]的定义为第i个数的斐波那契数值是dp[i]
确定递推公式
为什么这是一道非常简单的入门题目呢
因为题目已经把递推公式直接给我们了状态转移方程 dp[i] dp[i - 1] dp[i - 2];
dp数组如何初始化
题目中把如何初始化也直接给我们了如下 dp[0] 0dp[1] 1确定遍历顺序
从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的
举例推导dp数组
按照这个递推公式dp[i] dp[i - 1] dp[i - 2]我们来推导一下当N为10的时候dp数组应该是如下的数列
0 1 1 2 3 5 8 13 21 34 55
如果代码写出来发现结果不对就把dp数组打印出来看看和我们推导的数列是不是一致的。
以上就是动态规划五部曲 这在之后将贯穿所有动态规划类的题目
完整代码和复杂度分析
动态规划版本1定义dp数组
class Solution:def fib(self, n: int) - int:# 排除 Corner Caseif n 0:return 0# 创建 dp table dp [0] * (n 1)# 初始化 dp 数组dp[0] 0dp[1] 1# 遍历顺序: 由前向后。因为后面要用到前面的状态for i in range(2, n 1):# 确定递归公式/状态转移公式dp[i] dp[i - 1] dp[i - 2]# 返回答案return dp[n]时间复杂度O(n)空间复杂度O(n)
动态规划版本2不自定义dp数组仅使用3个变量来维护dp数组
class Solution:def fib(self, n: int) - int:if n 1:return ndp [0, 1]for i in range(2, n 1):total dp[0] dp[1]dp[0] dp[1]dp[1] totalreturn dp[1]时间复杂度O(n)空间复杂度O(1)
递归版本
class Solution:def fib(self, n: int) - int:if n 2:return nreturn self.fib(n - 1) self.fib(n - 2)时间复杂度O(2^n)空间复杂度O(n
