【动态规划】面试题 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. 题目解析

题目链接:面试题 08.01. 三步问题
一个小孩一次能上1,2,3层阶梯,求解到n阶台阶时有多少种走法。

1. 算法原理
每个动态规划问题我们都会按照如下方法去分析.
1.1 状态表示
也就是dp数组(也称dp表)中,dp[i]所代表的意思是什么?
这个状态表示怎么来的?
-
分析题目的要求得出来的----按照这题为例 dp[i]等于 走到第n个台阶时所有的走法
-
根据以往做题的经验+题目的要求得出来的(这个我们之后会用到)
-
分析问题中发现重复的子问题 (较难的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都已经初始化完
结合题目所给条件,我们不难发现:

所以初始化为: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,这里是Ppeua。平时主要更新C,数据结构算法,Linux与ROS…感兴趣就关注我bua! 文章目录 0. 题目解析1. 算法原理1.1 状态表示1.2 状态转移方程1.3初始化1.4 填表顺序1.5 返回值 2.算法代码 🐧 本篇是整个动态规划的…...
mac常见问题(三) macbook键盘溅上水怎么办?
多朋友在使用mac的时候难免会发生一些小意外,例如说本期要为大家说的macbook键盘溅上水或者其他的液体怎么办?不清楚的同学赶快get这项技能吧! 如果你不小心给你的MacBook键盘上溅了水或者其他液体,你需要超级快的把表面的液体清理…...
安全测试目录内容合集
基础知识 安全测试基础知识 安全测试-django防御安全策略 HTTP工作原理 靶场DVWA 安全测试网站-DWVA下载安装启动 DVWA-Command Injection DVWA-5.File upload 文件上传漏洞 DVWA-9.Weak Session IDs DVWA-XSS (Stored) DVWA-10.XSS (DOM)...
数据结构和算法(1):开始
算法概述 所谓算法,即特定计算模型下,旨在解决特定问题的指令序列 输入 待处理的信息(问题) 输出 经处理的信息(答案) 正确性 的确可以解决指定的问题 确定性 任一算法都可以描述为一个由基本操作组成的序…...
线下沙龙 | 从营销扩张到高效回款,游戏公司如何通过全链路运营实现高质量出海!
游戏出海,是近些年来中国产业的风暴出口,在2020至2023年期间保持着绝对的领航地位。公开数据显示,过去4年里,游戏在各类App出海份额中总体保持稳定,高达 64.9%。 但毕竟海外是陌生的市场,我们见过太多折戟沉…...
使用Jekyll + GitHub Pages搭建个人博客
本文将介绍如何使用Jekyll搭建个人博客,并部署在GitHub Pages上。 1.简介 Jekyll是一个强大的静态网站生成器,可以将Markdown、HTML、Liquid模板等文件转换为静态网站。Jekyll支持模板引擎、主题、插件、集成GitHub Pages等特性,可以帮助用…...
⽹络与HTTP 笔试题精讲1
OSI七层与TCP/IP 这个就是OSI参考模型,⽽实际我们现在的互联⽹世界是就是这个理论模型的落地叫做TCP/IP协议 TCP的三次握⼿与四次挥⼿ 客户端想要发送数据给服务端,在发送实际的数据之前,需要先在两端之间建⽴连接,数据发完以后也需要将该连接关闭。建⽴连接的过程就是我们…...
亲测有效:虚拟机安装gcc,报错Could not retrieve mirrorlist http://mirrorlist.centos.org
(网卡配置资料) 原因: 网络问题 报错详情: 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线性规划
本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考,主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等,本系列文章篇数较多,不定期更新,上半部分介绍无约束优化,…...
如何解决使用 ISPC 构建编译项目代码的时候出现_ISPCAlloc、_ISPCLaunch、_ISPCSync的连接器错误
一般在编译 ISPC 代码到时候,构建方法如下: $ ispc add.ispc -o add.o -h add.h $ g main.cpp add.o 但是在一些情况下连接器会报以下错误: $ 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)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
P1116 车厢重组(冒泡排序)
题目描述 在一个旧式的火车站旁边有一座桥,其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢,如果将桥旋转 180 180 180 度,则可以把相邻两节车厢的位置交换,用这种方法可以重新排列车厢的顺序…...
Android逆向学习(番外一)smali2java部分文件无法反编译的bug与修复方法
Android逆向学习(番外一)smali2java部分文件无法反编译的bug与修复方法 一、前言 昨天我和往常一样准备着android逆向(四)的博客,结果发现smali2java对某些文件无法进行逆向,我不知道windows会不会产生这…...
go语言基本操作---三
变量的内存和变量的地址 指针是一个代表着某个内存地址的值。这个内存地址往往是在内存中存储的另一个变量的值的起始位置。Go语言对指针的支持介于java语言和C/C语言之间,它即没有想Java语言那样取消了代码对指针的直接操作的能力,也避免了C/C语言中由…...
ArcGIS Enterprise + ArcGIS Pro 常用服务类型发布
发布前设置 门户连接 首先Pro需要先连接portal 添加portal门户地址,注意只到WA一级地址,并登录: 登录完成后,右键,设置为活动门户: 1. 发布动态地图服务 关联数据文件夹: 拖拽数据到地图…...
优思学院|亲和图案例:寻找六西格玛的项目
什么是亲和图? 亲和图(Affinity Diagram)主要功能在於分类归纳,协助在一堆杂乱无章的资料之中,有系统的归纳出几个大类,以利后续作业。通常先利用头脑风暴(Brainstorming)方式得到大…...
tomcat 的缓存机制
HTTP缓存:Tomcat支持HTTP缓存机制,可以通过设置响应头中的Cache-Control、Expires和ETag等字段来控制缓存策略。这些字段告诉浏览器是否可以缓存响应以及缓存的有效期等信息。 Servlet缓存:Tomcat还提供了Servlet缓存机制,它可以…...
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…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
