当前位置: 首页 > 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…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...