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…...
原神帧率解锁工具进程管理实战:解决启动冲突的3个鲜为人知的解决技巧
原神帧率解锁工具进程管理实战:解决启动冲突的3个鲜为人知的解决技巧 【免费下载链接】genshin-fps-unlock unlocks the 60 fps cap 项目地址: https://gitcode.com/gh_mirrors/ge/genshin-fps-unlock 问题现象:启动失败的常见场景 当你双击原神…...
weibo-rss:让微博内容主动找到你的高效订阅工具
weibo-rss:让微博内容主动找到你的高效订阅工具 【免费下载链接】weibo-rss 🍰 把喜欢的微博转为 RSS 订阅源 项目地址: https://gitcode.com/gh_mirrors/we/weibo-rss 在信息爆炸的时代,我们每天要处理大量碎片化内容。微博作为主流社…...
10个HTTPie CLI高级功能实战技巧:从入门到精通API调试
10个HTTPie CLI高级功能实战技巧:从入门到精通API调试 【免费下载链接】cli 🥧 HTTPie CLI — modern, user-friendly command-line HTTP client for the API era. JSON support, colors, sessions, downloads, plugins & more. 项目地址: https:/…...
如何构建LaTeX-Workshop的自动化测试与持续集成流程:开发者完整指南
如何构建LaTeX-Workshop的自动化测试与持续集成流程:开发者完整指南 【免费下载链接】LaTeX-Workshop Boost LaTeX typesetting efficiency with preview, compile, autocomplete, colorize, and more. 项目地址: https://gitcode.com/gh_mirrors/la/LaTeX-Worksh…...
电子元器件失效分析与预防实战指南
1. 电子元器件失效的底层逻辑剖析 电子元器件失效的本质是材料特性、环境应力与时间因素共同作用的结果。作为一名硬件工程师,我处理过数百例元器件失效案例,发现失效模式往往遵循"应力-损伤-失效"的因果链。理解这个链条,才能从根…...
大模型岗位大揭秘:面试官从不说的5个秘密!
本文作者通过自身经历,详细解析了五大与大模型相关的岗位区别,包括大模型算法工程师、大模型应用工程师、云厂商解决方案架构师、云厂商大模型解决方案架构师以及云厂商FDE大模型前沿部署工程师。文章从工作重心(模型vs客户)、面试…...
02_RAGFlow之DeepDoc深度文档理解技术
RAGFlow之DeepDoc深度文档理解技术 知识体系 RAGFlow知识体系 | -- 文档解析层 | -- DeepDoc核心能力 | -- 文档布局分析模型 | -- 模板化分块策略 | -- 多模态处理层 | -- 表格结构识别 | -- 公式识别 | -- 图文混排处理 | -- 分块优化层 | -- 可视化模板市场 |…...
2026届毕业生推荐的五大AI写作助手推荐榜单
Ai论文网站排名(开题报告、文献综述、降aigc率、降重综合对比) TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 维普AIGC检测系统,作为学术不端防范方面重要的工具,在高校与科研机构…...
企业做智能问数,最容易被低估的不是模型,而是人工预置工作量
在当前企业数据智能平台选型中,“大模型能力”常被视为决定成败的关键。然而,越来越多的实践表明:真正制约智能问数从 POC(概念验证)走向规模化落地的瓶颈,并非模型本身,而是隐藏在技术方案背后…...
Video-subtitle-remover:让视频创作者实现硬字幕无痕去除的AI解决方案
Video-subtitle-remover:让视频创作者实现硬字幕无痕去除的AI解决方案 【免费下载链接】video-subtitle-remover 基于AI的图片/视频硬字幕去除、文本水印去除,无损分辨率生成去字幕、去水印后的图片/视频文件。无需申请第三方API,本地实现。A…...
