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[i−1]+dp[i−2]+dp[i−3]
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经典问题:爬楼梯 爬楼梯 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。 Step1: 识别问题 这…...
示例:推荐一个基于第三方QRCoder.Xaml封装的二维码显示控件
一、目的:基于第三方QRCoder.Xaml封装的二维码控件,为了方便WPF调用 二、效果如下 功能包括:背景色,前景色,中心图片设置和修改大小,二维码设置等 三、环境 VS2022 四、使用方式 1、安装nuget包…...
阿里云服务器618没想到这么便宜,买早了!
2年前,我买了个服务器,租用服务器(ECS5)和网络宽带(1M),可以说是非常非常低的配置了。 当时5年的折扣力度最大,但是打完折后,价格依然要近3000多元。 最近看到阿里云618活…...
提升Python技能的七个函数式编程技巧
文章目录 📖 介绍 📖🏡 演示环境 🏡📒 文章内容 📒📝 递归📝 结构化模式匹配📝 不变性📝 纯函数📝 高阶函数📝 函数组合📝 惰性求值⚓️ 相关链接 ⚓️📖 介绍 📖 在现代编程中,虽然Python并不是一门纯粹的函数式编程语言,但函数式编程(Funct…...
微型操作系统内核源码详解系列五(五):cm3下Pendsv切换任务上篇
系列一:微型操作系统内核源码详解系列一:rtos内核源码概论篇(以freertos为例)-CSDN博客 系列二:微型操作系统内核源码详解系列二:数据结构和对象篇(以freertos为例)-CSDN博客 系列…...
Django测试平台搭建学习笔记1
一安装 pip离线安装requests2.32.0所需要的依赖: : 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所需要的依赖: : iniconfig (2…...
本地离线模型搭建指南-RAG架构实现
搭建一个本地中文大语言模型(LLM)涉及多个关键步骤,从选择模型底座,到运行机器和框架,再到具体的架构实现和训练方式。以下是一个详细的指南,帮助你从零开始构建和运行一个中文大语言模型。 本地离线模型搭…...
【IPython 使用技巧整理】
IPython 使用技巧整理 IPython 是一个交互式 Python 解释器,比标准 Python 解释器提供了更加强大的功能和更友好的使用体验。它为数据科学、机器学习和科学计算提供了强大的工具,是 Python 开发人员不可或缺的工具之一。本文将深入探讨 IPython 的各种使…...
什么是孪生素数猜想
什么是孪生素数猜想 素数p与素数p2有无穷多对 孪生素数的公式(详见百度百科:孪生素数公式) 利用素数的判定法则,可以得到以下的结论:“若自然数q与q2都不能被任何不大于的素数 整除,则q与q 2都是素数”…...
Python学习笔记16:进阶篇(五)异常处理
异常 在编程中,异常是指程序运行过程中发生的意外事件,这些事件通常中断了正常的指令流程。它们可能是由于错误的输入数据、资源不足、非法操作或其他未预料到的情况引起的。Python中,当遇到这类情况时,会抛出一个异常对象&#…...
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.什么是压力测试 压力测试考察当前软硬件环境下系统所能承受的最大负荷并帮助找出系统瓶颈所在。压测都是为了系统在线上的处理能力和稳定性维持在一个标准范围内,做到心中有数 使用压力测试,我们有希望找到很多种用其他测试方法更难发现的错误&#…...
C语言| 数组元素的删除
同数组元素的插入差不多。 数组元素的插入,是先移动要插入元素位置后面的所有元素,再插入新元素,长度1。 C语言| 数组的插入-CSDN博客 数组元素的删除,是先删除元素,再把后面的元素往前移动一位,而本程序…...
QListView、QTableView或QTreeView截取滚动区域(截长图)
本文以QTreeView为例,理论上继承自QAbstractScrollArea的类都支持本文所述的方法。 一.效果 一共5个文件夹,每个文件文件夹下有5个文件,先把文件夹展开,然后截图。将滚动条拖到居中位置,是为了证明截图对滚动条无影响 下面是截的图 二.原理 将滚动区域的viewport设置为…...
论文《Tree Decomposed Graph Neural Network》笔记
【TDGNN】本文提出了一种树分解方法来解决不同层邻域之间的特征平滑问题,增加了网络层配置的灵活性。通过图扩散过程表征了多跳依赖性(multi-hop dependency),构建了TDGNN模型,该模型可以灵活地结合大感受场的信息&…...
控制下属很简单,用好这3大管人绝招,再跳的刺头也不敢造次
控制下属很简单,用好这3大管人绝招,再跳的刺头也不敢造次 第一招:给压力 很多团队中的员工都是自己不带脑子工作,遇事就喜欢请示领导,让领导拿方案、拿决策。 还有一些人,推一下,他才动一下&a…...
2.APP测试-安卓adb抓取日志
1.打开手机的开发者模式,打开USB调试 (1)小米手机打开开发者模式: 【设置】-【我的设备】-【全部参数信息】-快速多次点击【OS版本】-进入开发者模式 (2)连接手机和电脑,手机打开USB调试 【设置…...
高考填报志愿选专业,要善于发掘自身优势
每年的高考季,如何填报志愿又再成为困扰家长以及学生的难题,可能在面对大量的专业时,无论是考生还是家长都不知道应该如何选择,好的专业孩子不一定有优势,感兴趣的冷门专业又担心日后找工作难。 实际上,专业…...
如何在 Ubuntu 14.04 上使用 HAProxy 实现 SSL 终止
前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。 简介 HAProxy,全称高可用代理,是一款流行的开源软件 TCP/HTTP 负载均衡器和代理解决方案,可在 Linu…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
GeoServer发布PostgreSQL图层后WFS查询无主键字段
在使用 GeoServer(版本 2.22.2) 发布 PostgreSQL(PostGIS)中的表为地图服务时,常常会遇到一个小问题: WFS 查询中,主键字段(如 id)莫名其妙地消失了! 即使你在…...
未授权访问事件频发,我们应当如何应对?
在当下,数据已成为企业和组织的核心资产,是推动业务发展、决策制定以及创新的关键驱动力。然而,未授权访问这一隐匿的安全威胁,正如同高悬的达摩克利斯之剑,时刻威胁着数据的安全,一旦触发,便可…...
