【蓝桥】动态规划-简单-破损的楼梯
题目

解题思路
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+9;
const long long p=1e9+7;
long long dp[N];//dp[i]表示走到第i级台阶的方案数
bool broken[N];//broken代表破损台阶的数组
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int x;cin>>x;broken[x]=true;//如果第x级台阶破损了,那就设置成true}dp[0]=1;//第1级台阶比较特殊,因为它只有一种走法,就是从第0级迈到第1级,所以单独列出if(!broken[1])//如果第一级台阶没有破损{dp[1]=1;}
//破损默认dp[1]为0for(int i=2;i<=n;i++)//如果第1级台阶坏了,那就从第2级台阶开始{if(broken[i]){continue;}dp[i]=(dp[i-1]+dp[i-2])%p;//因为一次可以迈1—2个台阶(即可以从i-1或i-2级迈到第i级),所以第i级的方案数等于i-2级的方案数 + i-1级的方案数}cout<<dp[n]<<endl;return 0;
}
内存图助解
初始状态
在读取输入之前,flag 和 dp 数组都被初始化为 0,n 和 m 未赋值。
n: 未初始化
m: 未初始化flag: [0, 0, 0, 0, 0, 0, 0] // flag[0] 到 flag[6]
dp: [0, 0, 0, 0, 0, 0, 0] // dp[0] 到 dp[6]
读取输入后的状态
读取 n = 6 和 m = 1 后,标记破损点 3。
n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0] // flag[3] 被标记为 1
dp: [0, 0, 0, 0, 0, 0, 0] // dp 数组未初始化
n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0]
dp: [1, 0, 0, 0, 0, 0, 0] // dp[0] = 1,因为起点不是破损点
第一步:计算 dp[1]
-
flag[1] = 0,不是破损点。 -
dp[1] = dp[0] = 1
n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0]
dp: [1, 1, 0, 0, 0, 0, 0]
第二步:计算 dp[2]
-
flag[2] = 0,不是破损点。 -
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0]
dp: [1, 1, 2, 0, 0, 0, 0]
第三步:计算 dp[3]
-
flag[3] = 1,是破损点,跳过。 -
dp[3] = 0
n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0]
dp: [1, 1, 2, 0, 0, 0, 0]
最终结果为
n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0]
dp: [1, 1, 2, 0, 2, 2, 4]
输出 dp[6],即到达终点的合法走法数量4
相关文章:
【蓝桥】动态规划-简单-破损的楼梯
题目 解题思路 完整代码 #include <bits/stdc.h> using namespace std; const int N1e59; const long long p1e97; long long dp[N];//dp[i]表示走到第i级台阶的方案数 bool broken[N];//broken代表破损台阶的数组 int main() {int n,m;cin>>n>>m;for(int …...
如何自定义软件安装路径及Scoop包管理器使用全攻略
如何自定义软件安装路径及Scoop包管理器使用全攻略 一、为什么无法通过WingetUI自定义安装路径? 问题背景: WingetUI是Windows包管理器Winget的图形化工具,但无法直接修改软件的默认安装路径。原因如下: Winget设计限制…...
107,【7】buuctf web [CISCN2019 华北赛区 Day2 Web1]Hack World
这次先不进入靶场 看到红框里面的话就想先看看uuid是啥 定义与概念 UUID 是 Universally Unique Identifier 的缩写,即通用唯一识别码。它是一种由数字和字母组成的 128 位标识符,在理论上可以保证在全球范围内的唯一性。UUID 的设计目的是让分布式系…...
STM32 ADC单通道配置
硬件电路 接线图: ADC基本结构图 代码配置 根据基本结构框图 1.定义结构体变量 //定义结构体变量 GPIO_InitTypeDef GPIO_InitStructure;//定义GPIO结构体变量 ADC_InitTypeDef ADC_InitStructure; //定义ADC结构体变量 2.开启RCC时钟 ADC、GPIO的时钟&#x…...
【技海登峰】Kafka漫谈系列(二)Kafka高可用副本的数据同步与选主机制
【技海登峰】Kafka漫谈系列(二)Kafka高可用副本的数据同步与选主机制 一. 数据同步 在之前的学习中有了副本Replica的概念,解决了数据备份的问题。我们还需要面临一个设计难题即:如何处理分区中Leader与Follwer节点数据同步不匹配问题所带来的风险,这也是保证数据高可用的…...
Spring的三级缓存如何解决循环依赖问题
循环依赖问题是在对象之间存在相互依赖关系,形成一个闭环,导致无法准确的完成对象的创建和初始化,当两个或多个对象彼此之间相互引用,这种相互引用形成一个循环时,就可能出现循环依赖问题。 在 Spring 框架中…...
Ext文件系统
文件内容属性 被打开的文件在内存中,没有被打开的文件在磁盘里文件系统的工作就是根据路径帮我们找到在磁盘上的文件 磁盘(硬件) 磁盘的存储结构 磁头在传动臂的运动下共同进退,向磁盘写入的时候是向柱面批量写入的 OS文件系统访…...
回溯算法---数独问题
回溯算法理论基础 回溯和递归密不可分,有回溯就有递归,所谓回溯就是基于一个叉树,可能是二叉树或者是三叉树,从root节点开始深度优先搜索遍历节点,当遍历到一个子节点时,回溯到上一个根节点选择另外一个子…...
蓝桥杯python基础算法(2-1)——排序
目录 一、排序 二、例题 P3225——宝藏排序Ⅰ 三、各种排序比较 四、例题 P3226——宝藏排序Ⅱ 一、排序 (一)冒泡排序 基本思想:比较相邻的元素,如果顺序错误就把它们交换过来。 (二)选择排序 基本思想…...
【课程笔记】信息隐藏与数字水印
文章总览:YuanDaiMa2048博客文章总览 【课程笔记】信息隐藏与数字水印 信号处理基础知识隐写系统隐写算法性能指标音频信号处理基础数字音频概念人类听觉系统与语音质量评价信息隐藏的原理数字指纹与版权保护盲水印与非盲水印私钥水印与公钥水印信息隐藏的研究层次信息隐藏与数…...
Page Assist实现deepseek离线部署的在线搜索功能
前面文章Mac 基于Ollama 本地部署DeepSeek离线模型 实现了deepseek的离线部署,但是部署完成虽然可以进行问答和交互,也有thinking过程,但是没办法像官方一样进行联网搜索。今天我们介绍一款浏览器插件Page Assist来实现联网搜索,完…...
composeUI中Box 和 Surface的区别
在 Jetpack Compose 中,Box 和 Surface 都是常用的布局组件,但它们的用途和功能有所不同。 Box 组件: 功能:Box 是一个用于将子组件堆叠在一起的布局容器,类似于传统 Android 中的 FrameLayout。用途:适用…...
【LeetCode】5. 贪心算法:买卖股票时机
太久没更了,抽空学习下。 看一道简单题。 class Solution:def maxProfit(self, prices: List[int]) -> int:cost -1profit 0for i in prices:if cost -1:cost icontinueprofit_ i - costif profit_ > profit:profit profit_if cost > i:cost iret…...
MySQL表的CURD
目录 一、Create 1.1单行数据全列插入 1.2多行数据指定列插入 1.3插入否则更新 1.4替换 2.Retrieve 2.1 select列 2.1.1全列查询 2.1.2指定列查询 2.1.3查询字段为表达式 2.1.4为查询结果指定别名 2.1.5结果去重 2.2where条件 2.3结果排序 2.4筛选分页结果 三…...
Java 如何覆盖第三方 jar 包中的类
目录 一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理 背景: 在我们日常的开发中,经常需要使用第三方的 jar 包,有时候我们会发现第三方的 jar 包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,…...
VSCode中使用EmmyLua插件对Unity的tolua断点调试
一.VSCode中搜索安装EmmyLua插件 二.创建和编辑launch.json文件 初始的launch.json是这样的 手动编辑加上一段内容如下图所示: 三.启动调试模式,并选择附加的进程...
【数据结构】_链表经典算法OJ(力扣/牛客第二弹)
目录 1. 题目1:返回倒数第k个节点 1.1 题目链接及描述 1.2 解题思路 1.3 程序 2. 题目2:链表的回文结构 2.1 题目链接及描述 2.2 解题思路 2.3 程序 1. 题目1:返回倒数第k个节点 1.1 题目链接及描述 题目链接: 面试题 …...
Spring Boot 2 快速教程:WebFlux优缺点及性能分析(四)
WebFlux优缺点 【来源DeepSeek】 Spring WebFlux 是 Spring 框架提供的响应式编程模型,旨在支持非阻塞、异步和高并发的应用场景。其优缺点如下: 优点 高并发与低资源消耗 非阻塞 I/O:基于事件循环模型(如 Netty)&am…...
自定义多功能输入对话框:基于 Qt 打造灵活交互界面
一、引言 在使用 Qt 进行应用程序开发时,我们经常需要与用户进行交互,获取他们输入的各种信息。QInputDialog 是 Qt 提供的一个便捷工具,可用于简单的输入场景,但当需求变得复杂,需要支持更多类型的输入控件࿰…...
基于springboot河南省旅游管理系统
基于Spring Boot的河南省旅游管理系统是一种专为河南省旅游行业设计的信息管理系统,旨在整合和管理河南省的旅游资源信息,为游客提供准确、全面的旅游攻略和服务。以下是对该系统的详细介绍: 一、系统背景与意义 河南省作为中国的中部省份&…...
COMSOL激光与电火花高斯热源作用下5.6版本两相流水平集仿真模型:流体传热-层流耦合研究
comsol激光、电火花(高斯热源)加工的水平集两相流仿真模型,5.6版本的,是流体传热—层流—两相流水平集耦合。在COMSOL Multiphysics 5.6中,模拟激光或电火花加工过程中的热源分布和流体行为,是一个相当有趣…...
别再ping IP了!手把手教你给ZeroTier虚拟网络里的设备起个‘好记’的名字(DNS/mDNS实战)
告别IP记忆困扰:ZeroTier网络中的智能命名方案实战指南 每次在ZeroTier虚拟网络中访问设备时,你是否也厌倦了反复查看和输入那串冗长的IP地址?想象一下,当你想连接家庭NAS时,只需输入nas.home就能立即访问,…...
如何选择适合的单北斗变形监测一体机以提升基础设施安全?
本文将重点讨论如何选择适合的单北斗变形监测一体机,以增强基础设施的安全性。在当前基础设施建设快速发展的背景下,单北斗GNSS的应用显得尤为重要。通过深入理解单北斗变形监测的原理,用户能够更好地把握设备的核心优势,尤其是在…...
BGE嵌入模型突破指南:解锁多模态检索增强的实战路径
BGE嵌入模型突破指南:解锁多模态检索增强的实战路径 【免费下载链接】FlagEmbedding Dense Retrieval and Retrieval-augmented LLMs 项目地址: https://gitcode.com/GitHub_Trending/fl/FlagEmbedding 在信息爆炸的时代,如何让机器精准理解人类语…...
零代码也能构建智能登录系统?Dify工作流让你告别繁琐的前端开发
零代码也能构建智能登录系统?Dify工作流让你告别繁琐的前端开发 【免费下载链接】Awesome-Dify-Workflow 分享一些好用的 Dify DSL 工作流程,自用、学习两相宜。 Sharing some Dify workflows. 项目地址: https://gitcode.com/GitHub_Trending/aw/Awes…...
ReaR实战:构建企业级Linux裸机灾难恢复体系
1. 为什么企业需要裸机灾难恢复方案 想象一下这样的场景:凌晨三点,机房突然响起刺耳的警报声。值班工程师冲进机房,发现核心数据库服务器已经宕机,硬盘指示灯全灭——这是一次严重的硬件故障。更糟糕的是,这台服务器上…...
从GigE Vision到千兆UDP:FPGA图像采集系统的灵活升级与10G MAC预留设计
从GigE Vision到千兆UDP:FPGA图像采集系统的灵活升级与10G MAC预留设计 在工业视觉和机器视觉领域,图像采集系统的带宽需求正以惊人的速度增长。随着4K、8K高分辨率相机的普及,以及多相机同步采集场景的增多,传统的千兆以太网接口…...
鸣潮帧率优化指南:用WaveTools工具箱实现高流畅度游戏体验
鸣潮帧率优化指南:用WaveTools工具箱实现高流畅度游戏体验 【免费下载链接】WaveTools 🧰鸣潮工具箱 项目地址: https://gitcode.com/gh_mirrors/wa/WaveTools 还在为鸣潮游戏中的画面卡顿、帧率不稳定而困扰吗?想要在激烈的战斗中获得…...
告别序列‘拉直’的暴力美学:手把手复现MaIR,体验保持图像局部与连续性的Mamba新玩法
告别序列“拉直”的暴力美学:手把手复现MaIR,体验保持图像局部与连续性的Mamba新玩法 在计算机视觉领域,图像修复任务(如去噪、超分、去模糊)一直是研究热点。传统方法往往将2D图像“拉直”为1D序列进行处理࿰…...
自动化周报生成:OpenClaw+GLM-4.7-Flash整合多平台数据
自动化周报生成:OpenClawGLM-4.7-Flash整合多平台数据 1. 为什么需要自动化周报 每周五下午,我的心情总是特别复杂。一方面期待着周末的到来,另一方面又要面对那个令人头疼的任务——写周报。相信很多技术从业者都有类似的经历:…...
