刷题记录 动态规划-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组件是一种列表类组件,类似我们之前介…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
