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

dp经典问题:爬楼梯

dp经典问题:爬楼梯


爬楼梯

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

Step1: 识别问题

这个问题要求我们计算 小孩上到第n阶台阶有多少种方法

Step2:定义状态

d p [ i ] < − 小孩上到第 n 阶台阶的方法数量,定义为第 i 个状态 dp[i] <- 小孩上到第n阶台阶的方法数量,定义为 第 i 个状态 dp[i]<小孩上到第n阶台阶的方法数量,定义为第i个状态

Step3:确定状态转移方程

这里 小孩每次可以上1阶,2阶或3阶 ,也就是说小孩可以从前1阶,2阶或者3阶上到当前台阶

也就是说当前状态由前三个状态决定

d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] + d p [ i − 3 ] dp[i]=dp[i-1]+dp[i-2]+dp[i-3] dp[i]=dp[i1]+dp[i2]+dp[i3]

Step4:确定初始状态和边界

d p [ 0 ] = 1 d p [ 1 ] = 1 d p [ 2 ] = 2 d p [ 3 ] = 4 dp[0]=1\\ dp[1]=1\\ dp[2]=2\\ dp[3]=4 dp[0]=1dp[1]=1dp[2]=2dp[3]=4

Step5:计算目标状态值

只需要从第四个状态开始自下而上的状态推导即可

代码

class Solution {
public:int waysToStep(int n) {if (n == 1) return 1;if (n == 2) return 2;if (n == 3) return 4;vector<int> dp(n + 1);dp[0] = 1;dp[1] = 1;dp[2] = 2;dp[3] = 4;const int mod = 1000000007;for (int i = 4; i <= n; ++i) {dp[i] = ((dp[i - 1] + dp[i - 2]) % mod + dp[i - 3]) % mod;}return dp[n];}
};

相关文章:

dp经典问题:爬楼梯

dp经典问题&#xff1a;爬楼梯 爬楼梯 三步问题。有个小孩正在上楼梯&#xff0c;楼梯有n阶台阶&#xff0c;小孩一次可以上1阶、2阶或3阶。实现一种方法&#xff0c;计算小孩有多少种上楼梯的方式。结果可能很大&#xff0c;你需要对结果模1000000007。 Step1: 识别问题 这…...

示例:推荐一个基于第三方QRCoder.Xaml封装的二维码显示控件

一、目的&#xff1a;基于第三方QRCoder.Xaml封装的二维码控件&#xff0c;为了方便WPF调用 二、效果如下 功能包括&#xff1a;背景色&#xff0c;前景色&#xff0c;中心图片设置和修改大小&#xff0c;二维码设置等 三、环境 VS2022 四、使用方式 1、安装nuget包&#xf…...

阿里云服务器618没想到这么便宜,买早了!

2年前&#xff0c;我买了个服务器&#xff0c;租用服务器&#xff08;ECS5&#xff09;和网络宽带&#xff08;1M&#xff09;&#xff0c;可以说是非常非常低的配置了。 当时5年的折扣力度最大&#xff0c;但是打完折后&#xff0c;价格依然要近3000多元。 最近看到阿里云618活…...

提升Python技能的七个函数式编程技巧

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 文章内容 📒📝 递归📝 结构化模式匹配📝 不变性📝 纯函数📝 高阶函数📝 函数组合📝 惰性求值⚓️ 相关链接 ⚓️📖 介绍 📖 在现代编程中,虽然Python并不是一门纯粹的函数式编程语言,但函数式编程(Funct…...

微型操作系统内核源码详解系列五(五):cm3下Pendsv切换任务上篇

系列一&#xff1a;微型操作系统内核源码详解系列一&#xff1a;rtos内核源码概论篇&#xff08;以freertos为例&#xff09;-CSDN博客 系列二&#xff1a;微型操作系统内核源码详解系列二&#xff1a;数据结构和对象篇&#xff08;以freertos为例&#xff09;-CSDN博客 系列…...

Django测试平台搭建学习笔记1

一安装 pip离线安装requests2.32.0所需要的依赖&#xff1a; : charset-normalizer<4,>2 (3.0.0b1) : idna<4,>2.5 (3.7) : urllib3<3,>1.21.1 (2.2.0) : certifi>2017.4.17 (2024.6.2) pip离线安装pytest8.2.0所需要的依赖&#xff1a; : iniconfig (2…...

本地离线模型搭建指南-RAG架构实现

搭建一个本地中文大语言模型&#xff08;LLM&#xff09;涉及多个关键步骤&#xff0c;从选择模型底座&#xff0c;到运行机器和框架&#xff0c;再到具体的架构实现和训练方式。以下是一个详细的指南&#xff0c;帮助你从零开始构建和运行一个中文大语言模型。 本地离线模型搭…...

【IPython 使用技巧整理】

IPython 使用技巧整理 IPython 是一个交互式 Python 解释器&#xff0c;比标准 Python 解释器提供了更加强大的功能和更友好的使用体验。它为数据科学、机器学习和科学计算提供了强大的工具&#xff0c;是 Python 开发人员不可或缺的工具之一。本文将深入探讨 IPython 的各种使…...

什么是孪生素数猜想

什么是孪生素数猜想 素数p与素数p2有无穷多对 孪生素数的公式&#xff08;详见百度百科&#xff1a;孪生素数公式&#xff09; 利用素数的判定法则&#xff0c;可以得到以下的结论&#xff1a;“若自然数q与q2都不能被任何不大于的素数 整除&#xff0c;则q与q 2都是素数”…...

Python学习笔记16:进阶篇(五)异常处理

异常 在编程中&#xff0c;异常是指程序运行过程中发生的意外事件&#xff0c;这些事件通常中断了正常的指令流程。它们可能是由于错误的输入数据、资源不足、非法操作或其他未预料到的情况引起的。Python中&#xff0c;当遇到这类情况时&#xff0c;会抛出一个异常对象&#…...

Mac 安装依赖后依旧报错 ModuleNotFoundError: No module named ‘Crypto‘

ModuleNotFoundError: No module named ‘Crypto’ 解决办法 pip uninstall pycryptodome pip uninstall pycrypto pip uninstall crypto pip install pycrypto...

【07】持久化-数据库选择和设计

1. 数据库选择 在比特币原始论文中,并没有提到要使用哪一个具体的数据库,它完全取决于开发者如何选择。Bitcoin Core ,最初由中本聪发布,现在是比特币的一个参考实现,它使用的是 LevelDB。 我们将要使用的是BoltDB。Bolt DB是一个纯键值存储的 Go 数据库。没有具体的数据…...

压力测试

1.什么是压力测试 压力测试考察当前软硬件环境下系统所能承受的最大负荷并帮助找出系统瓶颈所在。压测都是为了系统在线上的处理能力和稳定性维持在一个标准范围内&#xff0c;做到心中有数 使用压力测试&#xff0c;我们有希望找到很多种用其他测试方法更难发现的错误&#…...

C语言| 数组元素的删除

同数组元素的插入差不多。 数组元素的插入&#xff0c;是先移动要插入元素位置后面的所有元素&#xff0c;再插入新元素&#xff0c;长度1。 C语言| 数组的插入-CSDN博客 数组元素的删除&#xff0c;是先删除元素&#xff0c;再把后面的元素往前移动一位&#xff0c;而本程序…...

QListView、QTableView或QTreeView截取滚动区域(截长图)

本文以QTreeView为例,理论上继承自QAbstractScrollArea的类都支持本文所述的方法。 一.效果 一共5个文件夹,每个文件文件夹下有5个文件,先把文件夹展开,然后截图。将滚动条拖到居中位置,是为了证明截图对滚动条无影响 下面是截的图 二.原理 将滚动区域的viewport设置为…...

论文《Tree Decomposed Graph Neural Network》笔记

【TDGNN】本文提出了一种树分解方法来解决不同层邻域之间的特征平滑问题&#xff0c;增加了网络层配置的灵活性。通过图扩散过程表征了多跳依赖性&#xff08;multi-hop dependency&#xff09;&#xff0c;构建了TDGNN模型&#xff0c;该模型可以灵活地结合大感受场的信息&…...

控制下属很简单,用好这3大管人绝招,再跳的刺头也不敢造次

控制下属很简单&#xff0c;用好这3大管人绝招&#xff0c;再跳的刺头也不敢造次 第一招&#xff1a;给压力 很多团队中的员工都是自己不带脑子工作&#xff0c;遇事就喜欢请示领导&#xff0c;让领导拿方案、拿决策。 还有一些人&#xff0c;推一下&#xff0c;他才动一下&a…...

2.APP测试-安卓adb抓取日志

1.打开手机的开发者模式&#xff0c;打开USB调试 &#xff08;1&#xff09;小米手机打开开发者模式&#xff1a; 【设置】-【我的设备】-【全部参数信息】-快速多次点击【OS版本】-进入开发者模式 &#xff08;2&#xff09;连接手机和电脑&#xff0c;手机打开USB调试 【设置…...

高考填报志愿选专业,要善于发掘自身优势

每年的高考季&#xff0c;如何填报志愿又再成为困扰家长以及学生的难题&#xff0c;可能在面对大量的专业时&#xff0c;无论是考生还是家长都不知道应该如何选择&#xff0c;好的专业孩子不一定有优势&#xff0c;感兴趣的冷门专业又担心日后找工作难。 实际上&#xff0c;专业…...

如何在 Ubuntu 14.04 上使用 HAProxy 实现 SSL 终止

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。 简介 HAProxy&#xff0c;全称高可用代理&#xff0c;是一款流行的开源软件 TCP/HTTP 负载均衡器和代理解决方案&#xff0c;可在 Linu…...

Windows Defender Remover终极指南:深度解析系统安全组件移除技术

Windows Defender Remover终极指南&#xff1a;深度解析系统安全组件移除技术 【免费下载链接】windows-defender-remover A tool which is uses to remove Windows Defender in Windows 8.x, Windows 10 (every version) and Windows 11. 项目地址: https://gitcode.com/gh_…...

SEO推广系统与其他推广渠道的对比

SEO推广系统与其他推广渠道的对比 在现代商业环境中&#xff0c;各种推广渠道层出不穷&#xff0c;其中SEO推广系统和其他传统或新兴的推广渠道各有优劣。本文将从问题分析、原因说明、解决方法、注意事项和实用建议五个方面&#xff0c;深入探讨SEO推广系统与其他推广渠道的对…...

GESP2025年3月认证C++三级( 第一部分选择题(1-8))

&#x1f3af; 第1题&#xff1a;Base64魔法箱&#x1f4dc; 题目核心&#xff1a; &#x1f449; 每 3个字节 → 变成4个字节1、&#x1f9e0; 故事理解有一个魔法机器&#xff1a;&#x1f449; 每放进去 3个苹果 &#x1f34e;&#x1f34e;&#x1f34e;&#xff08;不足3个…...

基于胸部正位X光片的两阶段对比学习椎体压缩性骨折筛查框架文献速递-多模态医学影像最新进展

2026.4.2本研究提出一种基于胸部正位X光片的双阶段对比学习框架TADC-Net&#xff0c;通过模仿放射科医生的诊断流程&#xff0c;解决了器官遮挡和类间相似性等挑战&#xff0c;实现了椎体压缩性骨折的早期精准筛查&#xff0c;显著提升了诊断性能和临床辅助准确性。Title题目01…...

Open UI5 源代码解析之780:Label.js

源代码仓库: https://github.com/SAP/openui5 源代码位置:src\sap.m\src\sap\m\Label.js sap.m.Label 文件深度解析与项目作用说明 一、文件定位与整体职责 Label.js 位于 sap.m 组件库中,是一个非常基础却影响面极广的控件实现文件。它定义了 sap.m.Label 的完整行为,…...

解决WPS标题编号不从‘一‘开始的烦恼:新手必看避坑指南

WPS标题编号异常全解析&#xff1a;从问题根源到高阶应用技巧 刚接触WPS文字处理的新手们&#xff0c;经常会遇到一个令人困惑的现象——文档中的标题编号莫名其妙地从"二"或"三"开始&#xff0c;而不是预期的"一"。这种情况不仅影响文档美观&am…...

保姆级教程:在CentOS 8 Stream上从零部署Zabbix 6.4监控系统(Nginx+MariaDB 10.6+PHP 7.4)

企业级监控系统实战&#xff1a;CentOS 8 Stream上部署Zabbix 6.4全栈指南 在数字化转型浪潮中&#xff0c;IT基础设施监控已成为企业运维的核心支柱。Zabbix作为开源监控领域的标杆产品&#xff0c;其6.4版本带来了更强大的自动发现机制和可视化功能。本文将手把手带您完成从裸…...

告别网络调试焦虑:用STM32CubeMX+FreeRTOS,给LAN8720A和LWIP做个“健康检查”与性能小优化

STM32网络子系统深度优化&#xff1a;从连通性测试到工业级稳定性实战 当你熬夜调试的嵌入式设备终于能Ping通时&#xff0c;那种喜悦感堪比程序员第一次写出"Hello World"。但很快你会发现&#xff0c;真正的挑战才刚刚开始——那些在演示视频里永远不会出现的诡异断…...

为什么说降AI率不等于降质量从算法角度看本质

“用了工具处理&#xff0c;论文会不会变差&#xff1f;” 这是使用降AI率工具前很多同学最担心的问题。这篇文章从算法逻辑出发&#xff0c;把这个问题说清楚。 简短结论&#xff1a;好的降AI工具不会降低论文质量&#xff1b;差的工具会。判断哪个是好工具&#xff0c;这篇…...

用STM32CubeMX配置PWM捕获:从定时器选型到串口输出全流程

STM32CubeMX实战&#xff1a;PWM捕获全流程解析与调试技巧 在嵌入式开发中&#xff0c;精确测量PWM信号的周期和占空比是常见需求。本文将带你从零开始&#xff0c;使用STM32CubeMX和HAL库完成PWM捕获功能的完整实现。不同于简单的教程复制&#xff0c;我们会深入探讨两种捕获…...