刷题记录 动态规划-2: 509. 斐波那契数
题目:509. 斐波那契数
难度:简单
斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(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
相关文章:
刷题记录 动态规划-2: 509. 斐波那契数
题目:509. 斐波那契数 难度:简单 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) 0,F(1) 1 F(n…...
RDP协议详解
以下内容包含对 RDP(Remote Desktop Protocol,远程桌面协议)及其开源实现 FreeRDP 的较为系统、深入的讲解,涵盖协议概要、历史沿革、核心原理、安全机制、安装与使用方法、扩展与未来发展趋势等方面, --- ## 一、引…...
设计模式的艺术-观察者模式
行为型模式的名称、定义、学习难度和使用频率如下表所示: 1.如何理解观察者模式 一个对象的状态或行为的变化将导致其他对象的状态或行为也发生改变,它们之间将产生联动,正所谓“触一而牵百发”。为了更好地描述对象之间存在的这种一对多&…...
【C语言设计模式学习笔记1】面向接口编程/简单工厂模式/多态
面向接口编程可以提供更高级的抽象,实现的时候,外部不需要知道内部的具体实现,最简单的是使用简单工厂模式来进行实现,比如一个Sensor具有多种表示形式,这时候可以在给Sensor结构体添加一个enum类型的type,…...
Baklib如何优化企业知识管理提升团队协作与创新能力分析
内容概要 在现代企业中,知识管理已经成为提升竞争力的关键因素之一。Baklib作为一种全面的知识管理解决方案,致力于帮助企业高效整合和运用内部及外部知识资源。它通过建立统一的知识管理框架,打破了部门之间的信息壁垒,实现了跨…...
Dubbo view
1、 说说Dubbo核心的配置有哪些? 答: 配置 配置说明 dubbo:service 服务配置 dubbo:reference 引用配置 dubbo:protocol 协议配置 dubbo:application 应用配置 dubbo:module 模块配置 dubbo:registry 注册中心配置 dubbo:monitor 监控中心配置 dubbo:pr…...
分享刷题过程中有价值的两道题目
小编在这里先祝大家新的一年里所愿皆得,万事顺意,天天开心!!! 一.水仙花数 题目描述: 求100∼999中的水仙花数。若三位数ABCA^3B^3C^3,则称ABC为水仙花数。例如153,135333112527153&…...
蓝桥杯例题六
奋斗是一种态度,也是一种生活方式。无论我们面对什么样的困难和挑战,只要心怀梦想,坚持不懈地努力,就一定能够迈向成功的道路。每一次失败都是一次宝贵的经验,每一次挫折都是一次锻炼的机会。在困难面前,我…...
DeepSeek 详细使用教程
1. 简介 DeepSeek 是一款基于人工智能技术的多功能工具,旨在帮助用户高效处理和分析数据、生成内容、解答问题、进行语言翻译等。无论是学术研究、商业分析还是日常使用,DeepSeek 都能提供强大的支持。本教程将详细介绍 DeepSeek 的各项功能及使用方法。…...
《tcp/ip协议详解》,tcp/ip协议详解
TCP/IP协议(Transmission Control Protocol/Internet Protocol)是网络通信协议的一种,也被称为“Internet协议”,是Internet上运行的基本协议,广泛应用于各种网络环境和应用场合。以下是对TCP/IP协议的详细解析&#x…...
游戏引擎 Unity - Unity 设置为简体中文、Unity 创建项目
Unity Unity 首次发布于 2005 年,属于 Unity Technologies Unity 使用的开发技术有:C# Unity 的适用平台:PC、主机、移动设备、VR / AR、Web 等 Unity 的适用领域:开发中等画质中小型项目 Unity 适合初学者或需要快速上手的开…...
【数据结构】_时间复杂度相关OJ(力扣版)
目录 1. 示例1:消失的数字 思路1:等差求和 思路2:异或运算 思路3:排序+二分查找 2. 示例2:轮转数组 思路1:逐次轮转 思路2:三段逆置(经典解法) 思路3…...
[Java]异常
在程序运行时,如果遇到问题(比如除以零、文件找不到等),程序会发生异常。异常就像是程序的“错误提醒”,当程序运行中出错时,它会停止,给出一个错误信息。我们可以通过异常处理来控制这些错误&a…...
【C++语言】卡码网语言基础课系列----13. 链表的基础操作I
文章目录 背景知识链表1、虚拟头节点(dummyNode)2、定义链表节点3、链表的插入 练习题目链表的基础操作I具体代码实现 小白寄语诗词共勉 背景知识 链表 与数组不同,链表的元素存储可以是连续的,也可以是不连续的,每个数据除了存储本身的信息…...
Vue.js组件开发-实现图片浮动效果
使用Vue实现图片浮动效果 实现思路 将使用Vue的单文件组件(.vue)来实现图片浮动效果。主要思路是通过CSS的transform属性结合JavaScript的定时器来改变图片的位置,从而实现浮动效果。 代码实现 <template><!-- 定义一个包含图片…...
自制Windows系统(十一、Windows11GUI)
开源地址:下载(Work(Windows11gui).img) 上图 部分代码: void init_screen8(char *vram, int x, int y) { int *fat; unsigned char c; struct MEMMAN *memman (struct MEMMAN *) MEMMAN_ADDR; boxfill8(vram, x, 136, 0, …...
索罗斯的“反身性”(Reflexivity)理论:市场如何扭曲现实?(中英双语)
索罗斯的“反身性”(Reflexivity)理论:市场如何扭曲现实? 一、引言:市场是镜子,还是哈哈镜? 在传统经济学中,市场通常被认为是一个理性、有效的反映现实的系统。按照经典经济学理论…...
力扣257. 二叉树的所有路径(遍历思想解决)
Problem: 257. 二叉树的所有路径 文章目录 题目描述思路复杂度Code 题目描述 思路 遍历思想(利用二叉树的先序遍历) 利用先序遍历的思想,我门用一个List变量path记录当前先序遍历的节点,当遍历到根节点时,将其添加到另一个List变量res中&…...
使用朴素贝叶斯对散点数据进行分类
本文将通过一个具体的例子,展示如何使用 Python 和 scikit-learn 库中的 GaussianNB 模型,对二维散点数据进行分类,并可视化分类结果。 1. 数据准备 假设我们有两个类别的二维散点数据,每个类别包含若干个点。我们将这些点分别存…...
如何实现滑动列表功能
文章目录 1 概念介绍2 使用方法3 示例代码 我们在上一章回中介绍了沉浸式状态栏相关的内容,本章回中将介绍SliverList组件.闲话休提,让我们一起Talk Flutter吧。 1 概念介绍 我们在这里介绍的SliverList组件是一种列表类组件,类似我们之前介…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
