剑指 Offer 10- I. 斐波那契数列 - leetcode 剑指offer系列
发布日期:2021-06-29 07:11:48
浏览次数:3
分类:技术文章
本文共 1631 字,大约阅读时间需要 5 分钟。
题目难度: 简单
今天继续更新剑指 offer 系列, 这道题实在太经典了, 它也是动态规划的基础题目, 估计大家都见过, 今天就来复习一下吧~ 另外下面的做法还会有一些空间上的优化, 值得关注
若无意外, 每天晚上 6 点 45 分准时更新, 中间可能会穿插一些周赛题解. 大家在我的公众号"每日精选算法题"中的聊天框中回复 offer 就能看到该系列当前已经更新的文章了
大家有什么想法建议和反馈的话欢迎随时交流, 包括但不限于公众号聊天框/知乎私信评论等等~
题目描述
写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:
- F(0) = 0
- F(1) = 1
- F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
0 <= n <= 100
题目样例
示例 1
输入
n = 2
输出
1
示例 2
输入
n = 5
输出
5
题目思考
- 如何利用递推条件?
解决方案
思路
分析
- 初始化条件和递推式(转移方程)都给了, 这就是最基础的动态规划思想了: 保存已有信息, 新的信息通过已有信息计算得到(就是转移过程), 避免重复计算
- 这里引申一点, 动态规划的难点在于如何将具体问题进行转换, 以及如何找到转移方程
- 我的建议是遇到问题都可以先尝试分析相邻的值(数组的相邻元素, 图的相邻点), 看看它们是否存在一些关系; 另外还可以尝试增加维度/状态找相邻点, 以及找当前值与之前多个值的关系等等
- 感兴趣的小伙伴可以在我的公众号"每日精选算法题"中的聊天框中回复 股票, 那个系列里有几个比较进阶的动态规划题目
实现
- 定义 dp 数组, 初始化
dp[0] = 0, dp[1] = 1
- 然后从
2
开始循环直到n
, 每次套用dp[n] = dp[n-1] + dp[n-2]
即可 - 特别注意根据题目要求, 每次相加得到新的 dp 值时需要取模 (如果最后结果再取模的话, 对于 python 而言由于涉及大数操作, 速度会慢一些, 而对于 C/Java 等语言的话则可能会导致溢出)
- 优化
- 注意到当前 dp 值只和前面两个 dp 值有关, 所以我们完全可以只使用两个变量
pre
和prepre
, 分别代表当前下标的前一个和再上一个下标的 dp 值dp[n-1]
和dp[n-2]
. - 然后当前的 dp 值就更新为它们两个的和
- 最后更新当前 dp 值为新的
pre
, 原来的pre
就是新的prepre
了 - 而最终结果就是
pre
了, 因为遍历完 n 之后, 当前 dp 值已经更新为pre
了
- 注意到当前 dp 值只和前面两个 dp 值有关, 所以我们完全可以只使用两个变量
复杂度
- 时间复杂度
O(N)
- 需要遍历整个数组一遍
- 空间复杂度
O(1)
- 优化后只需要几个变量即可
代码
class Solution: def fib(self, n: int) -> int: if n < 2: # n小于2的情况, 根据初始化, 直接返回n即可 return n prepre, pre = 0, 1 for i in range(2, n + 1): # 同时更新新的prepre和pre, 这里利用了python的语言特性, 同时赋值的时候不会相互影响, 其他语言可能需要额外一个tmp变量来先保存原来的pre了 prepre, pre = pre, (prepre + pre) % 1000000007 return pre
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/106892319 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月07日 21时29分35秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
HDU4135 Co-prime【容斥原理】3方法
2019-04-29
GCD 容斥原理
2019-04-29
大学生活随笔
2019-04-29
The Boss on Mars(容斥原理)
2019-04-29
Confusing Date Format
2019-04-29
J - Super Sum UVA - 7720 (逆元与快速幂模板)
2019-04-29
Coprime (二分+容斥原理)
2019-04-29
HDU 4407 Sum (容斥原理)
2019-04-29
容斥原理(组合数学)总结
2019-04-29
心理与自我生活 2
2019-04-29
POJ 3159 Candies (差分约束 Dijkstra+优先队列 SPFA+栈)
2019-04-29
HDU 1907 John (Nim博弈 模板)
2019-04-29
HDU 1730 Northcott Game (Nim博弈)
2019-04-29
HDU 3790 最短路径问题 (dijkstra+路长和权值)
2019-04-29
HDU 1874 畅通工程续 (dijkstra +优先队列 模板+spfa)
2019-04-29
最短路径总结
2019-04-29
HDU 1848 Fibonacci again and again (SG函数 模板)
2019-04-29
POJ 2975 Nim (Nim的证明)
2019-04-29