当前位置: 首页 > news >正文

刷题记录 动态规划-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. 斐波那契数

题目&#xff1a;509. 斐波那契数 难度&#xff1a;简单 斐波那契数 &#xff08;通常用 F(n) 表示&#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始&#xff0c;后面的每一项数字都是前面两项数字的和。也就是&#xff1a; F(0) 0&#xff0c;F(1) 1 F(n…...

RDP协议详解

以下内容包含对 RDP&#xff08;Remote Desktop Protocol&#xff0c;远程桌面协议&#xff09;及其开源实现 FreeRDP 的较为系统、深入的讲解&#xff0c;涵盖协议概要、历史沿革、核心原理、安全机制、安装与使用方法、扩展与未来发展趋势等方面&#xff0c; --- ## 一、引…...

设计模式的艺术-观察者模式

行为型模式的名称、定义、学习难度和使用频率如下表所示&#xff1a; 1.如何理解观察者模式 一个对象的状态或行为的变化将导致其他对象的状态或行为也发生改变&#xff0c;它们之间将产生联动&#xff0c;正所谓“触一而牵百发”。为了更好地描述对象之间存在的这种一对多&…...

【C语言设计模式学习笔记1】面向接口编程/简单工厂模式/多态

面向接口编程可以提供更高级的抽象&#xff0c;实现的时候&#xff0c;外部不需要知道内部的具体实现&#xff0c;最简单的是使用简单工厂模式来进行实现&#xff0c;比如一个Sensor具有多种表示形式&#xff0c;这时候可以在给Sensor结构体添加一个enum类型的type&#xff0c;…...

Baklib如何优化企业知识管理提升团队协作与创新能力分析

内容概要 在现代企业中&#xff0c;知识管理已经成为提升竞争力的关键因素之一。Baklib作为一种全面的知识管理解决方案&#xff0c;致力于帮助企业高效整合和运用内部及外部知识资源。它通过建立统一的知识管理框架&#xff0c;打破了部门之间的信息壁垒&#xff0c;实现了跨…...

Dubbo view

1、 说说Dubbo核心的配置有哪些&#xff1f; 答&#xff1a; 配置 配置说明 dubbo:service 服务配置 dubbo:reference 引用配置 dubbo:protocol 协议配置 dubbo:application 应用配置 dubbo:module 模块配置 dubbo:registry 注册中心配置 dubbo:monitor 监控中心配置 dubbo:pr…...

分享刷题过程中有价值的两道题目

小编在这里先祝大家新的一年里所愿皆得&#xff0c;万事顺意&#xff0c;天天开心&#xff01;&#xff01;&#xff01; 一.水仙花数 题目描述&#xff1a; 求100∼999中的水仙花数。若三位数ABCA^3B^3C^3&#xff0c;则称ABC为水仙花数。例如153&#xff0c;135333112527153&…...

蓝桥杯例题六

奋斗是一种态度&#xff0c;也是一种生活方式。无论我们面对什么样的困难和挑战&#xff0c;只要心怀梦想&#xff0c;坚持不懈地努力&#xff0c;就一定能够迈向成功的道路。每一次失败都是一次宝贵的经验&#xff0c;每一次挫折都是一次锻炼的机会。在困难面前&#xff0c;我…...

DeepSeek 详细使用教程

1. 简介 DeepSeek 是一款基于人工智能技术的多功能工具&#xff0c;旨在帮助用户高效处理和分析数据、生成内容、解答问题、进行语言翻译等。无论是学术研究、商业分析还是日常使用&#xff0c;DeepSeek 都能提供强大的支持。本教程将详细介绍 DeepSeek 的各项功能及使用方法。…...

《tcp/ip协议详解》,tcp/ip协议详解

TCP/IP协议&#xff08;Transmission Control Protocol/Internet Protocol&#xff09;是网络通信协议的一种&#xff0c;也被称为“Internet协议”&#xff0c;是Internet上运行的基本协议&#xff0c;广泛应用于各种网络环境和应用场合。以下是对TCP/IP协议的详细解析&#x…...

游戏引擎 Unity - Unity 设置为简体中文、Unity 创建项目

Unity Unity 首次发布于 2005 年&#xff0c;属于 Unity Technologies Unity 使用的开发技术有&#xff1a;C# Unity 的适用平台&#xff1a;PC、主机、移动设备、VR / AR、Web 等 Unity 的适用领域&#xff1a;开发中等画质中小型项目 Unity 适合初学者或需要快速上手的开…...

【数据结构】_时间复杂度相关OJ(力扣版)

目录 1. 示例1&#xff1a;消失的数字 思路1&#xff1a;等差求和 思路2&#xff1a;异或运算 思路3&#xff1a;排序&#xff0b;二分查找 2. 示例2&#xff1a;轮转数组 思路1&#xff1a;逐次轮转 思路2&#xff1a;三段逆置&#xff08;经典解法&#xff09; 思路3…...

[Java]异常

在程序运行时&#xff0c;如果遇到问题&#xff08;比如除以零、文件找不到等&#xff09;&#xff0c;程序会发生异常。异常就像是程序的“错误提醒”&#xff0c;当程序运行中出错时&#xff0c;它会停止&#xff0c;给出一个错误信息。我们可以通过异常处理来控制这些错误&a…...

【C++语言】卡码网语言基础课系列----13. 链表的基础操作I

文章目录 背景知识链表1、虚拟头节点(dummyNode)2、定义链表节点3、链表的插入 练习题目链表的基础操作I具体代码实现 小白寄语诗词共勉 背景知识 链表 与数组不同&#xff0c;链表的元素存储可以是连续的&#xff0c;也可以是不连续的&#xff0c;每个数据除了存储本身的信息…...

Vue.js组件开发-实现图片浮动效果

使用Vue实现图片浮动效果 实现思路 将使用Vue的单文件组件&#xff08;.vue&#xff09;来实现图片浮动效果。主要思路是通过CSS的transform属性结合JavaScript的定时器来改变图片的位置&#xff0c;从而实现浮动效果。 代码实现 <template><!-- 定义一个包含图片…...

自制Windows系统(十一、Windows11GUI)

开源地址&#xff1a;下载&#xff08;Work(Windows11gui).img&#xff09; 上图 部分代码&#xff1a; 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)理论:市场如何扭曲现实?(中英双语)

索罗斯的“反身性”&#xff08;Reflexivity&#xff09;理论&#xff1a;市场如何扭曲现实&#xff1f; 一、引言&#xff1a;市场是镜子&#xff0c;还是哈哈镜&#xff1f; 在传统经济学中&#xff0c;市场通常被认为是一个理性、有效的反映现实的系统。按照经典经济学理论…...

力扣257. 二叉树的所有路径(遍历思想解决)

Problem: 257. 二叉树的所有路径 文章目录 题目描述思路复杂度Code 题目描述 思路 遍历思想(利用二叉树的先序遍历) 利用先序遍历的思想&#xff0c;我门用一个List变量path记录当前先序遍历的节点&#xff0c;当遍历到根节点时&#xff0c;将其添加到另一个List变量res中&…...

使用朴素贝叶斯对散点数据进行分类

本文将通过一个具体的例子&#xff0c;展示如何使用 Python 和 scikit-learn 库中的 GaussianNB 模型&#xff0c;对二维散点数据进行分类&#xff0c;并可视化分类结果。 1. 数据准备 假设我们有两个类别的二维散点数据&#xff0c;每个类别包含若干个点。我们将这些点分别存…...

如何实现滑动列表功能

文章目录 1 概念介绍2 使用方法3 示例代码 我们在上一章回中介绍了沉浸式状态栏相关的内容&#xff0c;本章回中将介绍SliverList组件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1 概念介绍 我们在这里介绍的SliverList组件是一种列表类组件&#xff0c;类似我们之前介…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...

李沐--动手学深度学习--GRU

1.GRU从零开始实现 #9.1.2GRU从零开始实现 import torch from torch import nn from d2l import torch as d2l#首先读取 8.5节中使用的时间机器数据集 batch_size,num_steps 32,35 train_iter,vocab d2l.load_data_time_machine(batch_size,num_steps) #初始化模型参数 def …...

【阅读笔记】MemOS: 大语言模型内存增强生成操作系统

核心速览 研究背景 ​​研究问题​​&#xff1a;这篇文章要解决的问题是当前大型语言模型&#xff08;LLMs&#xff09;在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色&#xff0c;但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成&#xff08;RA…...

ffmpeg(三):处理原始数据命令

FFmpeg 可以直接处理原始音频和视频数据&#xff08;Raw PCM、YUV 等&#xff09;&#xff0c;常见场景包括&#xff1a; 将原始 YUV 图像编码为 H.264 视频将 PCM 音频编码为 AAC 或 MP3对原始音视频数据进行封装&#xff08;如封装为 MP4、TS&#xff09; 处理原始 YUV 视频…...

轻量安全的密码管理工具Vaultwarden

一、Vaultwarden概述 Vaultwarden主要作用是提供一个自托管的密码管理器服务。它是Bitwarden密码管理器的第三方轻量版&#xff0c;由国外开发者在Bitwarden的基础上&#xff0c;采用Rust语言重写而成。 &#xff08;一&#xff09;Vaultwarden镜像的作用及特点 轻量级与高性…...