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…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
