[LeetCode] 面试题08.01 三步问题

题目描述:

三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。

示例1:

 输入:n = 3 
 输出:4
 说明: 有四种走法

示例2:

 输入:n = 5
 输出:13

提示:

  1. n范围在[1, 1000000]之间

题目链接:

. - 力扣(LeetCode)

解题主要思路:

其实这题跟 "第N个泰波那契数" 是一类型的,动态规划即可。

  • 首先我们先理清dp[i]表示什么?dp[i]表示到达i位置时,一共有多少方式。
  • 其次我们需要理清状态转移方程,dp[i]表示dp[i]表示到达i位置时一共有多少方式,且小孩一次可以上1阶、2阶或3阶,那么我们可以理解为:

                小孩从dp[i-3]一次上3阶;

                小孩从dp[i-2]一次上2阶;

                小孩从dp[i-1]一次上1阶;

        因此状态转移方程可以表示为dp[i] = dp[i-3] + dp[i-2] + dp[i-1];不过题目说了结果可能很大,            需要对结果模1000000007,所以我们每相加一次就需要对数据取模。

  • 然后我们需要注意dp表的初始化以及边界问题,例如当i = 1时,dp[i-3]就越界了,因此当i [1,3]时我们需要单独拿出来判断。
  • 最后我们要注意dp表填表顺序以及返回值即可。

解题代码:

class Solution {
public:const int MOD = 1e9+7;  // 1000000007int waysToStep(int n) {// 边界情况if (n == 1 || n == 2) return n;if (n == 3) return 4;vector<int> dp(n+1);  // 创建dp表dp[1] = 1, dp[2] = 2, dp[3] = 4;  // 初始化for (int i = 4; i <= n; ++i){   // 构建dp表dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;}return dp[n];}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/463577.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Mac 配置SourceTree集成云效

1、背景 工作使用的是自己的笔记本&#xff0c;一个是比较卡&#xff0c;在一个是敏感信息比较多还是使用公司的电脑&#xff0c;但是系统是Mac就很麻烦&#xff0c;在网上找了帖子记录一下 2、配置 打开终端 ssh-keygen -t rsa #一直回车就行 cd .ssh cat id_rsa.pub #查…

【快速上手】pyspark 集群环境下的搭建(Yarn模式)

目录 前言&#xff1a; 一、安装步骤 安装前准备 1.第一步&#xff1a;安装python 2.第二步&#xff1a;在bigdata01上安装spark 3.第三步&#xff1a;同步bigdata01中的spark到bigdata02和03上 二、启动 三、可打开yarn界面查看任务 前言&#xff1a; 上一篇介绍的是…

使用Python多线程抓取某图网数据并下载图片

前言 在互联网开发领域&#xff0c;数据抓取是一项非常实用的技术。通过数据抓取&#xff0c;我们可以从网页上获取所需的信息&#xff0c;并将其转化为结构化数据&#xff0c;以便进一步分析或使用。本文将介绍如何利用Python编写一个多线程程序来抓取网页上的图片数据&#…

《IMM交互式多模型滤波MATLAB实践》专栏目录,持续更新……

专栏链接&#xff1a;https://blog.csdn.net/callmeup/category_12816762.html 专栏介绍 关于IMM的例程 双模型EKF&#xff1a; 【逐行注释】基于CV/CT模型的IMM|MATLAB程序|源代码复制后即可运行&#xff0c;无需下载三模型EKF&#xff1a; 【matlab代码】3个模型的IMM例程&…

鸿蒙开发案例:指南针

【1】引言&#xff08;完整代码在最后面&#xff09; 在本文中&#xff0c;我们将介绍如何使用鸿蒙系统&#xff08;HarmonyOS&#xff09;开发一个简单的指南针应用。通过这个案例&#xff0c;你可以学习如何使用传感器服务、状态管理以及UI构建等基本技能。 【2】环境准备 …

人工智能的发展与未来:从Yann LeCun的观点谈起

引言 在当今的人工智能&#xff08;AI&#xff09;领域&#xff0c;AGI&#xff08;通用人工智能&#xff09;已成为热门话题。许多专家认为&#xff0c;随着技术的不断发展&#xff0c;AGI的实现只是时间问题。然而&#xff0c;Yann LeCun——图灵奖得主、Meta首席AI科学家&a…

【The Art of Unit Testing 3_自学笔记06】3.4 + 3.5 单元测试核心技能之:函数式注入与模块化注入的解决方案简介

文章目录 3.4 函数式依赖注入技术 Functional injection techniques3.5 模块化依赖注入技术 Modular injection techniques 写在前面 上一篇的最后部分对第三章后续内容做了一个概括性的梳理&#xff0c;并给出了断开依赖项的最简单的实现方案&#xff0c;函数参数值注入法。本…

电磁兼容(EMC):整改案例(六)Y电容过大导致雷击浪涌炸机

目录 1. 异常现象 2. 原因分析 3. 整改方案 4. 总结 1. 异常现象 某金属外壳带接地线的产品按GB/T 17626.5进行雷击浪涌测试&#xff0c;在L&#xff0c;N线对PE进行4kV浪涌电压测试时&#xff0c;出现炸机现象&#xff0c;AC-DC电源芯片损坏。而在L&#xff0c;N线间进行2…

代码之眼,陈欣的xml解密之路

第一章 在未来的世界里&#xff0c;科技已经发展到了令人难以想象的地步。人工智能、量子计算和生物技术交织在一起&#xff0c;创造了一个全新的社会形态。在这个世界中&#xff0c;有一个名为“代码守护者”的组织&#xff0c;专门负责维护全球信息系统的安全和稳定。 陈欣是…

L0G1000:Linux+InternStudio 闯关作业

1. 配置基础环境 首先&#xff0c;打开 Intern Studio 界面&#xff0c;点击 创建开发机 配置开发机系统。 InternStudio 填写 开发机名称 后&#xff0c;点击 选择镜像 使用 Cuda11.7-conda 镜像&#xff0c;然后在资源配置中&#xff0c;使用 10% A100 * 1 的选项&#xff…

爬虫笔记22——当当网图书详情页静、动态数据爬取

当当网动态数据爬取 静态数据爬取动态数据爬取接口参数的获取 静态数据爬取 进入图书详情&#xff0c;这里的图书数据信息比如标题、价格、图片都是非结构化数据&#xff0c;可以使用xpath语法提取。是很简单的数据采集了&#xff0c;就不细说了。 动态数据爬取 滑到下面这里的…

使用pathview在线渲染KEGG Pathway Map,给感兴趣的基因、化合物添加颜色

导读&#xff1a; 通过将用户提供的基因表达定量数据&#xff0c;化合物定量数据映射并渲染到相关的KEGG通路图上&#xff0c;能够帮助我们直观且系统地研究基因、酶、化合物间的关系。 KEGG通路图简介 KEGG PATHWAY数据库是一系列手动绘制的图形图谱的集合&#xff0c;称为…

自动化测试工具Ranorex Studio(二十一)-适配一个已存在的对象库

通过录制一个手工测试场景我们创建了一个对象库。录制期间用到的每个UI元素都在库中创建了一个新的条目。默认情况下&#xff0c;一个新的Ranorex Studio项目包含一个库文件(*.rxrep)&#xff0c;这个文件可以被多个录制模块或代码模块使用。 图&#xff1a;一个库的文件视图…

OpenSLL下载,环境变量配置

https://slproweb.com/products/Win32OpenSSL.html 环境变量 新建一个path为安装选择的目录的bin路径

【MyBatis】【基于轻量型架构的WEB开发】课程 课后习题 章节测试

mybatis关联查询、缓存、注解 一. 单选题 1. 下列关于 <collection> 元素的描述正确的是&#xff08;&#xff09;。 A. MyBatis 就是通过 <collection> 元素来处理一对多关联关系的 B. <collection> 元素的属性与 <association> 元素完全相同 C.…

JavaEE-多线程上

文章目录 线程概述进程/线程多线程的作用JVM关于线程资源的规范关于Java程序的运行原理 并发与并行并发(concurrency)并行(parallellism)并发编程与并行编程 线程的调度策略分时调度模型抢占式调度模型 创建线程线程类分析入门实现线程的第一种方式实现线程的第二种方式 线程的…

SQL 常用语句

目录 我的测试环境 学习文档 进入数据库 基础通关测验 语句-- 查 展示数据库&#xff1b; 进入某个数据库&#xff1b; 展示表&#xff1a; 展示某个表 desc 查询整个表&#xff1a; 查询特定列&#xff1a; 范围查询 等于特定值 不等于 介于 特定字符查询 Li…

[MySQL]DQL语句(一)

查询语句是数据库操作中最为重要的一系列语法。查询关键字有 select、where、group、having、order by、imit。其中imit是MySQL的方言&#xff0c;只在MySQL适用。 数据库查询又分单表查询和多表查询&#xff0c;这里讲一下单表查询。 基础查询 # 查询指定列 SELECT * FROM …

【Unity】鼠标点击获取世界坐标位置:物体移动至鼠标点击的位置

需求说明 鼠标点击3D场景时&#xff0c;可以获取其所在的世界坐标&#xff1b; 鼠标点击3D物体时&#xff0c;可以获取该物体&#xff1b; 鼠标点击3D物体时&#xff0c;可以让玩家移动至该物体&#xff1b; 成果展示 Scene部分 关于仓库栏的设置&#xff0c;物体如何进入…

使用nvm切换node版本失败

​ 使用nvm切换node版本失败&#xff08;原node版本v20.14.0&#xff0c;我使用nvm use 16.9.1切换node版本后&#xff0c;显示Now using node v16.9.1可当我使用命令node -v查看当前node版本时还是v20.14.0&#xff0c;意味着版本切换失败&#xff09;&#xff1a; 这个原因大…