DP第一天:力扣● 理论基础 ● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯
● 理论基础
DP大约五种问题:
动规基础(斐波那契数列、爬楼梯);背包问题;股票问题;打家劫舍;子序列问题。
要搞清楚:
- DP数组及其下标的含义;
- DP数组如何初始化;
- 递推公式;
- 遍历顺序;
- 打印DP数组;
无论难易,动态规划都可以用这5步来深入理解,即动规五部曲。因为对于动规,如果没有方法论的话,可能简单题目可以顺手一写就过,难一点就不知道如何下手了。
● 509. 斐波那契数
简单题也养成五部曲的习惯。
DP数组及其下标的含义:dp[i]是第i个斐波那契数。
DP数组如何初始化(dp[0]=0;dp[1]=1)、递推公式(dp[i]=dp[i-1]+dp[i-2])、遍历顺序(一层for循环,是从小到大递推所以从小到大遍历)、打印DP数组(设置n为一个不太大的数打印序列来检查正确性)这些都是直接能知道的。
代码如下:注意是返回dp[n]不是dp[n-1],所以一开始数组大小得是n+1个。
class Solution {
public:int fib(int n) {if(n==0)return 0;vector<int> dp(n+1);dp[0]=0;dp[1]=1;for(int i=2;i<=n;++i){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
};
● 70. 爬楼梯
n=1,2,3,4的方法数依次是1,2,3,5(全是1步1种,一个2步3种,2个2步1种),找规律发现还是一个斐波那契额数列。所以五部曲跟上一题相同。注意dp数组初始化的元素个数和返回的下标。
class Solution {
public:int climbStairs(int n) {if(n==1)return 1;vector<int> dp(n);dp[0]=1;dp[1]=2;//初始化,下标0是n=1for(int i=2;i<n;++i){dp[i]=dp[i-1]+dp[i-2];}return dp[n-1];}
};
● 746. 使用最小花费爬楼梯
五部曲:
- DP数组及其下标的含义:dp[i]是从底部(注意从0/从1开始都可以)到第i层的最低花费。要返回的还是dp数组最后一个数dp[n]。
- DP数组如何初始化:dp[0]=0,dp[1]=0(也是0,因为可以从1开始);
- 递推公式:递推公式是要从之前的dp序列得到dp[i],所以我们要立足下标i,根据题目意思,要想到达i,有两种选择:上一节台阶跨一步,上上一节台阶跨两步。取决于两种情况哪一种花费更低,所以用min:dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])。
- 遍历顺序:仍然是从小到大;
- 打印DP数组:
发现数组下标含义、初始化、递推都是要仔细思考的,要做到一致统一。
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {if(cost.size()==1)return cost[0];int n=cost.size();vector<int> dp(n+1);dp[0]=0;//初始化dp[1]=0;for(int i=2;i<=n;++i){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);cout<<dp[i]<<" ";//打印检查}return dp[n];//底部到n个台阶的时间}
};
相关文章:
DP第一天:力扣● 理论基础 ● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯
● 理论基础 DP大约五种问题: 动规基础(斐波那契数列、爬楼梯);背包问题;股票问题;打家劫舍;子序列问题。 要搞清楚: DP数组及其下标的含义;DP数组如何初始化&#x…...
Android Studio 安装Flutter插件但是没法创建项目
Android Studio 安装Flutter插件但是没法创建项目 如果你在Android Studio已经安装了Dart、Flutter插件,但是不能创建Flutter项目。 原因是因为Android Studio的版本更新,Android APK Support这个插件没被选中。 一旦勾选这个插件之后,就能…...
新春快乐(烟花、春联)【附源码】
新春快乐 一: C语言 -- 烟花二:Python -- 春联三:Python -- 烟花四:HTML -- 烟花 一: C语言 – 烟花 运行效果: #include <graphics.h> #include <math.h> #include <time.h> #include…...
nextcloud 优化扩展
cd /config vi config.php #ONLYOFFICE allow_local_remote_servers > true, #应用商店加速 appstoreenabled > true, appstoreurl > https://www.orcy.net/ncapps/v2/, #nginx配置调优 add_header Strict-Transport-Security max-age15552000; add…...
【CSS】css如何实现字体大小小于12px?
【CSS】css如何实现字体大小小于12px? 问题解决方案transform: scale(0.5)(常用)SVG 矢量图设置text 问题 文字需要显示为12px,但是小于12px的,浏览器是显示不来的 解决方案 transform: scale(0.5)(常用࿰…...
【Langchain+Streamlit】旅游聊天机器人
【LangchainStreamlit】打造一个旅游问答AI-CSDN博客 项目线上地址,无需openai秘钥可直接体验:http://101.33.225.241:8502/ github地址:GitHub - jerry1900/langchain_chatbot: langchainstreamlit打造的一个有memory的旅游聊天机器人&…...
〖大前端 - ES6篇②〗- let和const
说明:该文属于 大前端全栈架构白宝书专栏,目前阶段免费,如需要项目实战或者是体系化资源,文末名片加V!作者:哈哥撩编程,十余年工作经验, 从事过全栈研发、产品经理等工作,目前在公司…...
JAVA设计模式之代理模式详解
代理模式 1 代理模式介绍 在软件开发中,由于一些原因,客户端不想或不能直接访问一个对象,此时可以通过一个称为"代理"的第三者来实现间接访问.该方案对应的设计模式被称为代理模式. 代理模式(Proxy Design Pattern ) 原始定义是:让你能够提供对象的替代…...
vivo发布2023 年度科技创新;阿里全新AI代理,可模拟人类操作手机
vivo 发布 2023 年度十大产品技术创新 近日,vivo 发布了「2023 年度科技创新」十大产品技术创新榜单,并将这些技术分为了 4 个板块。 「四大蓝科技」为 vivo 在去年推出的全新技术品牌,涵盖蓝晶芯片技术栈、蓝海续航系统、蓝心大模型、蓝河操…...
【制作100个unity游戏之23】实现类似七日杀、森林一样的生存游戏15(附项目源码)
本节最终效果演示 文章目录 本节最终效果演示系列目录前言实现树倒下的效果拾取圆木砍树消耗卡路里斧头手臂穿模问题处理源码完结 系列目录 前言 欢迎来到【制作100个Unity游戏】系列!本系列将引导您一步步学习如何使用Unity开发各种类型的游戏。在这第23篇中&…...
python巧用定理判断素数
目录 判断一个数n是否是素数 求一个数的素因数个数 求大于等于指定数的最小素数 在数论中有三个非常重要的关于素数的定理 1、任何数都可以表示成若干个素数的乘积 2、任意数的素因子一个大于根号n的自然数,另一个与其对应的因子则必小于根号n。 3、除了2和3以…...
2023年总结
人们总说时间会改变一切,但事实上你得自己来。 今年开始给自己的时间读书、工作、生活都加上一个2.0的release版本号,相比过去的一年还是有很多进步的。 就跟git commit一样,一步一步提交优化,年底了发个版本。用李笑来的话说&am…...
Git中为常用指令配置别名
目录 1 前言 2 具体操作 2.1 创建.bashrc文件 2.2 添加指令 2.3 使其生效 2.4 测试 1 前言 在Git中有一些常用指令比较长,当我们直接输入,不仅费时费力,还容易出错。这时候,如果能给其取个简短的别名,那么事情就…...
STM32内部Flash
目录 一、内部Flash简介 二、内部Flash构成 1. 主存储器 2. 系统存储区 3. 选项字节 三、内部Flash写入过程 1. 解锁 2. 页擦除 3. 写入数据 四、工程空间分布 某工程的ROM存储器分布映像: 1. 程序ROM的加载与执行空间 2. ROM空间分布表 一、内部Flash…...
html5 audio video
DOMException: play() failed because the user didn‘t interact with the document first.-CSDN博客 不可用: 可用: Google Chrome Close AutoUpdate-CSDN博客...
LoveWall v2.0Pro社区型校园表白墙源码
校园表白墙,一个接近于社区类型的表白墙,LoveWall。 源码特色; 点赞, 发评论, 发弹幕, 多校区, 分享页, 涉及违禁物等名词进行检测! 安装教程: 环境要求;…...
Flink cdc3.0动态变更表结构——源码解析
文章目录 前言源码解析1. 接收schema变更事件2. 发起schema变更请求3. schema变更请求具体处理4. 广播刷新事件并阻塞5. 处理FlushEvent6. 修改sink端schema 结尾 前言 上一篇Flink cdc3.0同步实例 介绍了最新的一些功能和问题,本篇来看下新功能之一的动态变更表结…...
WWW 2024 | 时间序列(Time Series)和时空数据(Spatial-Temporal)论文总结
WWW 2024已经放榜,本次会议共提交了2008篇文章,research tracks共录用约400多篇论文,录用率为20.2%。本次会议将于2024年5月13日-17日在新加坡举办。 本文总结了WWW 2024有关时间序列(Time Series)和时空数据…...
代码随想录算法——数组
目录 1、二分查找法 2、移除元素 3、有序数组的平方 4、长度最小的子数组 5、螺旋矩阵II 1、二分查找法 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在…...
Linux第45步_通过搭建“DNS服务器”学习图形化配置工具
学习的意义:通过搭建“DNS服务器”,来学习“图形化配置工具”。“DNS服务器”,我们用不到,但为后期移植linux系统服务,因为在移植系统时,需要用到这个“图形化配置工具”。 1、“menuconfig图形化配置工具…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...
