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

[动态规划] (一) LeetCode 1137.第N个泰波那契数

[动态规划] (一) LeetCode 1137.第N个泰波那契数

文章目录

      • [动态规划] (一) LeetCode 1137.第N个泰波那契数
        • 题目解析
        • 解题思路
          • 状态表示
          • 状态转移方程
          • 初始化和填表顺序
          • 返回值
        • 代码实现
        • 总结
        • 空间优化
          • 代码实现
        • 总结

1137. 第 N 个泰波那契数

题目解析

image-20231028220409948

解题思路
状态表示

(1) 题目要求

(2) 经验+题目要求

(3) 分析问题发现重复子问题

dp[i]的含义:dp[i]表示第N个泰波纳切数。

状态转移方程

由题意得:

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
初始化和填表顺序

初始化:填表时保证不越界

填表顺序:保证之前的状态已经计算过了,所以是从左向右

返回值

题目要求+状态表示

返回第n个泰波那契数:return dp[n]。

代码实现
class Solution {
public:int tribonacci(int n) {//处理边界情况if(n == 0) return 0;else if(n == 1 || n == 2) return 1;//1.创建dp表vector<int> dp(n+1);//2.初始化dp[0] = 0, dp[1] = 1, dp[2] = 1;for(int i = 3; i <= n; i++){//3.填表dp[i] = dp[i-1] + dp[i-2] + dp[i-3];}//返回值return dp[n];}
};

image-20231028215404127

总结

细节1:注意处理边界情况。

细节2:开辟容器时初始化(n+1)个空间,数组下标从0开始。

细节3:遍历完整的n,i <= n

时间复杂度:O(n)

空间复杂度:O(n)

空间优化

滚动数组:

dp[3] = dp[2] + dp[1] + dp[0]

dp[4] = dp[3] + dp[2] + dp[1],没有使用到dp[0]

dp[5] = dp[4] + dp[3] + dp[2],没有使用到dp[1], dp[0]。

造成了空间的浪费,所以我们可以定义4个变量a, b, c, d来循环写入dp[i]。

a = 0, b = 1, c = 1, d = a+b+c

a = b, b = c, c = d, d = a+b+c(如果反过来,就会让 a = b = c 和d一样了)

代码实现
class Solution {
public:int tribonacci(int n) {if(n == 0) return 0;else if(n == 1 || n == 2) return 1;int a = 0, b = 1, c = 1;int d = 0;for(int i = 3; i <= n; i++){d = a + b + c;a = b, b = c, c = d;}return d;}
};

image-20231028221407298

总结

时间复杂度:O(N) 空间复杂度:O(1)

相关文章:

[动态规划] (一) LeetCode 1137.第N个泰波那契数

[动态规划] (一) LeetCode 1137.第N个泰波那契数 文章目录 [动态规划] (一) LeetCode 1137.第N个泰波那契数题目解析解题思路状态表示状态转移方程初始化和填表顺序返回值 代码实现总结空间优化代码实现 总结 1137. 第 N 个泰波那契数 题目解析 解题思路 状态表示 (1) 题目要…...

SystemVerilog语法中,在Class中引用层次化信号

在class中可以像在verilog中一样&#xff0c;直接在class中引用层次化信号。示例如下&#xff1a; 1.DUT模块&#xff0c;文件名为top.v。 module top (input clk ,input rst_n ,//总线信号 input wr_n ,input rd_n ,input cs0_n ,input cs7_n …...

磁盘的结构(磁道,扇区,盘面,柱面,物理地址)

目录 1.磁盘、磁道、扇区的概念1.磁盘2.磁道3.扇区 2.如何在磁盘中读/写数据3.盘面、柱面的概念4.磁盘的物理地址1.根据地址读取一个“块” 5.磁盘的分类1.活动头磁道2.固定头磁盘3.根据盘片是否可更换 1.磁盘、磁道、扇区的概念 1.磁盘 磁盘的表面由一些磁性物质组成&#xf…...

uni-app集成uni-simple-router,报错:Uncaught ReferenceError: ROUTES is not defined

参考连接&#xff1a;GitHub - SilurianYang/uni-read-pages: read pages.json file to generate the routes table 作用&#xff1a;配置 vue.config.js 通过 webpack注入全局变量 问题&#xff1a;缺少Webpack 配置环境 方法&#xff1a; 项目根目录下打开终端&#xff0c;…...

几个常用的nosql数据库的操作方式

dynamoDB 键 partition key&#xff1a;分区键 定义&#xff1a;分区键是用于分布数据存储的主键&#xff0c;每个项&#xff08;Item&#xff09;在表中都必须有一个唯一的分区键值。 特点&#xff1a; 唯一性&#xff1a;每个分区键值在表中必须是唯一的&#xff0c;这是因为…...

如何使用 nvm-windows 这个工具来管理你电脑上的Node.js版本

nvm-windows 是一个用于管理在 Windows 上安装的多个 Node.js 版本的工具。以下是安装和使用 nvm-windows 的步骤&#xff1a; 第1步&#xff1a;下载 nvm-windows 访问 nvm-windows 的 GitHub发布页面.下载最新版本的 nvm-setup.zip 文件。 第2步&#xff1a;安装 nvm-wind…...

公司电脑禁用U盘的方法

公司电脑禁用U盘的方法 安企神U盘管理系统下载使用 在这个复杂的数据时代&#xff0c;保护公司数据的安全性至关重要。其中&#xff0c;防止未经授权的数据泄露是其中的一个关键环节。U盘作为一种常用的数据传输工具&#xff0c;也成为了潜在的安全风险。因此&#xff0c;公司…...

Elasticsearch 7.X版本常用语法语句

文章目录 监控相关 API查看健康状况查看所有节点查看所有节点详细信息查看主节点查看所有索引查看所有分片 索引管理创建索引查看索引查看索引字段类型修改索引字段删除索引别名给索引添加别名查询某个索引下的别名给索引更换别名给索引解绑别名一个别名绑定多个索引查询index_…...

Python分享之数学与随机数 (math包,random包)

我们在Python运算中看到Python最基本的数学运算功能。此外&#xff0c;math包补充了更多的函数。当然&#xff0c;如果想要更加高级的数学功能&#xff0c;可以考虑选择标准库之外的numpy和scipy项目&#xff0c;它们不但支持数组和矩阵运算&#xff0c;还有丰富的数学和物理方…...

Linux 基本语句_8_C语言_文件控制

为了解决多个进程同时操作一个文件&#xff0c;产生一些情况&#xff0c;通常对文件进行上锁&#xff0c;已解决对共享文件的竞争 对打开文件进行各种操作&#xff1a; int fcentl(int fd, int cmd, .../*arg*/如果cmd与锁操作有关&#xff0c;那么fcentl函数的第三个参数就要…...

博通BCM575系列 RDMA 网卡驱动 bnxt_re 分析(一)

简介 整个BCM系列驱动分成以太网部分(bnxt_en.ko)和RDMA部分(bnxt_re.ko), 两个模块之间通过内核的auxiliary_bus进行管理.我们主要分析下bnxt_re驱动. 代码结构 这个驱动的核心是 qplib_fp.c, 这个文件主要包含了驱动的数据路径, 包括Post Send, Post Recv, Poll CQ流程的实…...

ExcelPatternTool 开箱即用的Excel工具包现已发布!

文章目录 ExcelPatternTool功能特点&#xff1a;快速开始使用说明常规类型高级类型Importable注解Exportable注解IImportOption导入选项IExportOption导出选项单元格样式StyleMapping样式映射使用数据库作为数据源 示例Sample1&#xff1a;不同类型字段导出Sample2&#xff1a;…...

Navicat for MySQL 视图创建使用方法

创建视图步骤&#xff1a; 点击新建&#xff1b;选择视图&#xff1b;点击视图创建工具&#xff1b;可以在左侧拖拽表到工作区&#xff1b;选择表字段进行连线...

计算机视觉的相机选型

#你一般什么时候会用到GPT?# 目前市面上的工业相机大多是基于CCD&#xff08;ChargeCoupled Device&#xff09;或CMOS&#xff08;Complementary Metal Oxide Semiconductor&#xff09;芯片的相机。一般CCD制造工艺更加复杂&#xff0c;也会更贵一点&#xff01; 1、CCD工…...

实体店做商城小程序如何

互联网电商深入各个行业&#xff0c;传统线下店商家无论产品销售还是服务业&#xff0c;仅靠以往的经营模式&#xff0c;很难拓展到客户&#xff0c;老客流失严重&#xff0c;同时渠道单一&#xff0c;无法实现外地客户购物及线上客户赋能等。 入驻第三方平台有优势但也有不足…...

sql-50练习题0-5

sql练习题0-5题 前言数据库表结构介绍学生表课程表成绩表教师表 0-1 查询"01"课程比"02"课程成绩高的学生的信息及课程分数0-2查询"01"课程比"02"课程成绩小的学生的信息及课程分数0-3查询平均成绩大于等于60分的同学的学生编号和学生…...

Flutter框架实现登录注册功能,不连接数据库

要在Flutter框架中实现登录和注册功能&#xff0c;而不连接数据库&#xff0c;可以使用本地存储来存储用户信息。以下是一个简单的示例&#xff0c;演示如何使用本地存储来实现登录和注册功能。 首先&#xff0c;我们需要添加 shared_preferences 插件到 pubspec.yaml 文件中&…...

持续集成部署-k8s-部署利器-Helm

这里写目录标题 1. Helm 是什么?2. 快速安装 Helm2.1 前置条件2.2 Helm 版本与 K8s 版本对应关系2.3 离线安装 Helm3. Helm 常用命令1. Helm 是什么? Helm 是一个用于 Kubernetes 应用程序部署和管理的开源工具。它可以帮助简化 Kubernetes 应用程序的打包、发布、配置和升级…...

替换所有的问号

这篇也是凑数的 哈哈.... 稍后会整合到算法通关第三关白银挑战 . 描述 : 给你一个仅包含小写英文字母和 ? 字符的字符串 s&#xff0c;请你将所有的 ? 转换为若干小写字母&#xff0c;使最终的字符串不包含任何 连续重复 的字符。 注意 : 不能 修改非 ? 字符 . 题目 : …...

NCCL后端

"NCCL" 代表 "NVIDIA Collective Communications Library"&#xff0c;"NVIDIA 集体通信库"&#xff0c;它是一种由 NVIDIA 开发的用于高性能计算的通信库。NCCL 专门设计用于加速 GPU 群集之间的通信&#xff0c;以便在并行计算和深度学习等领域…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...