当前位置: 首页 > 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…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...