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

【动态规划】面试题 08.01. 三步问题

在这里插入图片描述
Halo,这里是Ppeua。平时主要更新C++,数据结构算法,Linux与ROS…感兴趣就关注我bua!

文章目录

  • 0. 题目解析
  • 1. 算法原理
    • 1.1 状态表示
    • 1.2 状态转移方程
    • 1.3初始化
    • 1.4 填表顺序
    • 1.5 返回值
  • 2.算法代码

在这里插入图片描述

🐧 本篇是整个动态规划的入门篇章,题目或许可以通过暴力或者其他方法求解但在这里,我们只讨论与动态规划相关的解法.

🐧 Gitee链接:面试题 08.01. 三步问题

0. 题目解析

image-20230822020607564

题目链接:面试题 08.01. 三步问题

一个小孩一次能上1,2,3层阶梯,求解到n阶台阶时有多少种走法。

b4166c93c336d2f26d989c454b1b567

1. 算法原理

每个动态规划问题我们都会按照如下方法去分析.

1.1 状态表示

也就是dp数组(也称dp表)中,dp[i]所代表的意思是什么?

这个状态表示怎么来的?

  1. 分析题目的要求得出来的----按照这题为例 dp[i]等于 走到第n个台阶时所有的走法

  2. 根据以往做题的经验+题目的要求得出来的(这个我们之后会用到)

  3. 分析问题中发现重复的子问题 (较难的dp问题的状态表示往往由若干个子状态一起表示)

1.2 状态转移方程

这也就是如何求出dp[i]

我们观察发现,dp[i]可以由前三个台阶推出来.

例如:到台阶4的时候,可以由台阶一,台阶二,台阶三的步数走出来

具体的如下:可以由台阶1跳三格,台阶2跳两格,台阶3跳一格走到(注意这是一次跳的,而不是总共完成这么多格,所以只会有一种方法而不是多种)

所以如果我想要到台阶4的方法数就等于由台阶1的方法数+台阶2的方法数+台阶3的方法数.

所以dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

1.3初始化

核心思想为:保证数组不越界的情况下,完成我们的状态转移方程.

观察我们的状态转移方程,我们会发现,我们需要的值是i的前三个(i-1,i-2,i-3).所以当i=3时,最小位(i-3)此时为0.

这意味着:我们要保证不越界,我们的dp表要从i=3开始填,也就是i=0、1、2都已经初始化完

结合题目所给条件,我们不难发现:

158368f06fff3b646f26d7f44c7ee6f

所以初始化为:dp[0]=0,dp[1]=1,dp[2]=2

注意,当题目所给n的范围小于2时,我们访问dp[2]会造成越界.所以需要特判一下

1.4 填表顺序

为了保证填写当前状态的时候,所需要的状态已经计算过了,我们从左向右

1.5 返回值

根据我们的dp[i]表示走到第i个台阶的方法数,而题目要求我们返回 走到第n个台阶的方法数,所以我们直接返回dp[n]即可

2.算法代码

class Solution {
int N=1000000007;
public:int waysToStep(int n) {vector<int>dp(n+1,0);if(n==1||n==2)return n;dp[0]=0,dp[1]=1,dp[2]=2,dp[3]=4;//o(n)时间复杂度 o(n)时间复杂度for(int i=4;i<=n;i++){dp[i]=((dp[i-1]%N+dp[i-2])%N+dp[i-3]%N)%N;}return dp[n];}
};

时间复杂度:o(n)

空间复杂度:o(n)

可以使用滚动数组的方法将空间复杂度优化到o(1)级别.

观察状态转移方程.我们发现,虽然我们开辟了n个大小的空间,但我们计算第i个的时候,只会用到前三个的值,这意味着在[0,i-4]这段区间中的数组空间都是浪费的.所以我们可以单独创建三个变量来表示所需要的状态值,来取代这个数组,从而优化空间复杂度.

空间,但我们计算第i个的时候,只会用到前三个的值,这意味着在[0,i-4]这段区间中的数组空间都是浪费的.所以我们可以单独创建三个变量来表示所需要的状态值,来取代这个数组,从而优化空间复杂度.

相关文章:

【动态规划】面试题 08.01. 三步问题

Halo&#xff0c;这里是Ppeua。平时主要更新C&#xff0c;数据结构算法&#xff0c;Linux与ROS…感兴趣就关注我bua&#xff01; 文章目录 0. 题目解析1. 算法原理1.1 状态表示1.2 状态转移方程1.3初始化1.4 填表顺序1.5 返回值 2.算法代码 &#x1f427; 本篇是整个动态规划的…...

mac常见问题(三) macbook键盘溅上水怎么办?

多朋友在使用mac的时候难免会发生一些小意外&#xff0c;例如说本期要为大家说的macbook键盘溅上水或者其他的液体怎么办&#xff1f;不清楚的同学赶快get这项技能吧&#xff01; 如果你不小心给你的MacBook键盘上溅了水或者其他液体&#xff0c;你需要超级快的把表面的液体清理…...

安全测试目录内容合集

基础知识 安全测试基础知识 安全测试-django防御安全策略 HTTP工作原理 靶场DVWA 安全测试网站-DWVA下载安装启动 DVWA-Command Injection DVWA-5.File upload 文件上传漏洞 DVWA-9.Weak Session IDs DVWA-XSS (Stored) DVWA-10.XSS (DOM)...

数据结构和算法(1):开始

算法概述 所谓算法&#xff0c;即特定计算模型下&#xff0c;旨在解决特定问题的指令序列 输入 待处理的信息&#xff08;问题&#xff09; 输出 经处理的信息&#xff08;答案&#xff09; 正确性 的确可以解决指定的问题 确定性 任一算法都可以描述为一个由基本操作组成的序…...

线下沙龙 | 从营销扩张到高效回款,游戏公司如何通过全链路运营实现高质量出海!

游戏出海&#xff0c;是近些年来中国产业的风暴出口&#xff0c;在2020至2023年期间保持着绝对的领航地位。公开数据显示&#xff0c;过去4年里&#xff0c;游戏在各类App出海份额中总体保持稳定&#xff0c;高达 64.9%。 但毕竟海外是陌生的市场&#xff0c;我们见过太多折戟沉…...

使用Jekyll + GitHub Pages搭建个人博客

本文将介绍如何使用Jekyll搭建个人博客&#xff0c;并部署在GitHub Pages上。 1.简介 Jekyll是一个强大的静态网站生成器&#xff0c;可以将Markdown、HTML、Liquid模板等文件转换为静态网站。Jekyll支持模板引擎、主题、插件、集成GitHub Pages等特性&#xff0c;可以帮助用…...

⽹络与HTTP 笔试题精讲1

OSI七层与TCP/IP 这个就是OSI参考模型,⽽实际我们现在的互联⽹世界是就是这个理论模型的落地叫做TCP/IP协议 TCP的三次握⼿与四次挥⼿ 客户端想要发送数据给服务端,在发送实际的数据之前,需要先在两端之间建⽴连接,数据发完以后也需要将该连接关闭。建⽴连接的过程就是我们…...

亲测有效:虚拟机安装gcc,报错Could not retrieve mirrorlist http://mirrorlist.centos.org

&#xff08;网卡配置资料&#xff09; 原因&#xff1a; 网络问题 报错详情&#xff1a; One of the configured repositories failed (未知),and yum doesnt have enough cached data to continue. At this point the onlysafe thing yum can do is fail. There are a few …...

机器人中的数值优化(十二)——带约束优化问题简介、LP线性规划

本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考&#xff0c;主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等&#xff0c;本系列文章篇数较多&#xff0c;不定期更新&#xff0c;上半部分介绍无约束优化&#xff0c;…...

如何解决使用 ISPC 构建编译项目代码的时候出现_ISPCAlloc、_ISPCLaunch、_ISPCSync的连接器错误

一般在编译 ISPC 代码到时候&#xff0c;构建方法如下&#xff1a; $ ispc add.ispc -o add.o -h add.h $ g main.cpp add.o 但是在一些情况下连接器会报以下错误&#xff1a; $ g main.cpp add.o Undefined symbols for architecture x86_64:"_ISPCAlloc", refer…...

Hadoop 集群一直处于安全模式,强制退出后出现数据丢失警告。解决方法

文章目录 安全模式相关命令分析集群为什么一直处于安全模式解决方法 安全模式相关命令 # 查看安全模式状态 hdfs dfsadmin -safemode get# 进入安全模式 hdfs dfsadmin -safemode enter# 离开安全模式 hdfs dfsadmin -safemode leave# 强制退出安全模式 hdfs dfsadmin -safemo…...

四旋翼飞行器基本模型(MatlabSimulink)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

P1116 车厢重组(冒泡排序)

题目描述 在一个旧式的火车站旁边有一座桥&#xff0c;其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢&#xff0c;如果将桥旋转 180 180 180 度&#xff0c;则可以把相邻两节车厢的位置交换&#xff0c;用这种方法可以重新排列车厢的顺序…...

Android逆向学习(番外一)smali2java部分文件无法反编译的bug与修复方法

Android逆向学习&#xff08;番外一&#xff09;smali2java部分文件无法反编译的bug与修复方法 一、前言 昨天我和往常一样准备着android逆向&#xff08;四&#xff09;的博客&#xff0c;结果发现smali2java对某些文件无法进行逆向&#xff0c;我不知道windows会不会产生这…...

go语言基本操作---三

变量的内存和变量的地址 指针是一个代表着某个内存地址的值。这个内存地址往往是在内存中存储的另一个变量的值的起始位置。Go语言对指针的支持介于java语言和C/C语言之间&#xff0c;它即没有想Java语言那样取消了代码对指针的直接操作的能力&#xff0c;也避免了C/C语言中由…...

ArcGIS Enterprise + ArcGIS Pro 常用服务类型发布

发布前设置 门户连接 首先Pro需要先连接portal 添加portal门户地址&#xff0c;注意只到WA一级地址&#xff0c;并登录&#xff1a; 登录完成后&#xff0c;右键&#xff0c;设置为活动门户&#xff1a; 1. 发布动态地图服务 关联数据文件夹&#xff1a; 拖拽数据到地图…...

优思学院|亲和图案例:寻找六西格玛的项目

什么是亲和图&#xff1f; 亲和图&#xff08;Affinity Diagram&#xff09;主要功能在於分类归纳&#xff0c;协助在一堆杂乱无章的资料之中&#xff0c;有系统的归纳出几个大类&#xff0c;以利后续作业。通常先利用头脑风暴&#xff08;Brainstorming&#xff09;方式得到大…...

tomcat 的缓存机制

HTTP缓存&#xff1a;Tomcat支持HTTP缓存机制&#xff0c;可以通过设置响应头中的Cache-Control、Expires和ETag等字段来控制缓存策略。这些字段告诉浏览器是否可以缓存响应以及缓存的有效期等信息。 Servlet缓存&#xff1a;Tomcat还提供了Servlet缓存机制&#xff0c;它可以…...

laravel 压缩文件与解压文件

一、引入第三方类 composer require chumper/zipper二、第三方类配置 providers>[Chumper\Zipper\ZipperServiceProvider::class ]aliases > [Zipper > Chumper\Zipper\Zipper::class ]三、压缩解压缩实例 <?php namespace App\Http\Controllers\Upload; use A…...

kind搭建k8s集群用于测试

安装kind 需要先安装go kind基于go开发 #第一种安装方式#修改go源加快下载速度 go env -w GOPROXYhttps://goproxy.cn,direct #直接下载安装kind最新版本 go install sigs.k8s.io/kindlatest #进入GOPATH目录找到bin目录下kind执行程序 移动到环境变量里 mv ./kind /usr/local…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...