D33|动态规划!启程!
1.动态规划五部曲:
1)确定dp数组(dp table)以及下标的含义
2)确定递推公式
3)dp数组如何初始化
4)确定遍历顺序
5)举例推导dp数组
2.动态规划应该如何debug
找问题的最好方式就是把dp数组打印出来,看看究竟是不是按照自己思路推导的!
509.斐波那契数
初始思路:
class Solution {public int fib(int n) {if(n==0){return 0;}int[] dp = new int[n+1];dp[0] = 0;dp[1] = 1;for(int i = 2;i<n+1;i++){dp[i] = dp[i-1]+dp[i-2];}return dp[n];}
}
题解复盘:
题解更加清晰,首先按照动态规划五部曲进行分析:
1)确定dp数组以及下标的含义
dp[i]的定义为:第i个数的斐波那契数值是dp[i]
2)确定递推公式
状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
3)dp数组如何初始化
dp[0] = 0;
dp[1] = 1;
4)确定遍历顺序
从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的。
5)举例推导dp数组
0 1 1 2 3 5 8 13 21 34 55
压缩空间版本的题解:
class Solution {public int fib(int n) {if (n < 2) return n;int a = 0, b = 1, c = 0;for (int i = 1; i < n; i++) {c = a + b;a = b;b = c;}return c;}
}
70.爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
初始思路:
1)确定dp数组以及下标的含义:
dp[i]的定义为:表示爬到第i个台阶不同方法的数量。
2)确定递推公式:
dp[i] = dp[i - 1] + dp[i - 2]
3)dp数组如何初始化
dp[1] = 1;爬一层台阶只有一种方法
dp[2] = 2;爬两层台阶可以一次爬两层也可以爬两个一层。
4)确定遍历顺序
从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的。
5)举例推导dp数组
1,2,3,5,8,13,21,34
class Solution {public int climbStairs(int n) {if(n<=2){return n;}int a = 1;int b = 2;int c = 0;for(int i = 3;i<n+1;i++){c = a + b;a = b;b = c;}return c;}
}
746. 使用最小花费爬楼梯
初始思路:
这道题目就是在不同的爬楼梯方案中,挑选出来最小花费的爬楼梯方案。
唯一需要斟酌的地方就是我究竟是让其从第0阶台阶开始攀爬,还是从第1阶台阶开始攀爬。
1)确定dp数组以及下标的含义:
dp[i]的定义为:表示爬到第i个台阶所需要的最小花费。
2)确定递推公式:
dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
3) dp数组如何初始化
dp[0] = 0;dp[1] = 0;dp[2] = min(dp[0]+cost[0],cost[1]+dp[1]);
4) 确定遍历顺序
由前到后
5)举例推导dp数组

0,0,10,15
class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp = new int[cost.length+1];dp[0] = 0;dp[1] = 0;for(int i = 2;i<=cost.length;i++){dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[cost.length];}
}
题解复盘:
基本一致
相关文章:
D33|动态规划!启程!
1.动态规划五部曲: 1)确定dp数组(dp table)以及下标的含义 2)确定递推公式 3)dp数组如何初始化 4)确定遍历顺序 5)举例推导dp数组 2.动态规划应该如何debug 找问题的最好方式就是把…...
C语言----文件操作(二)
在上一篇文章中我们简单介绍了在C语言中文件是什么以及文件的打开和关闭操作,在实际工作中,我们不仅仅是要打开和关闭文件,二是需要对文件进行增删改写。本文将详细介绍如果对文件进行安全读写。 一,以字符形式读写文件ÿ…...
oracle 10046事件跟踪
10046事件是一个很好的排查sql语句执行缓慢的内部事件,具体设置方式如下: 根据10046事件跟踪SQL语句 1、 alter session set events 10046 trace name context forever,level 12; 2、执行SQL语句 3、关闭10046事件 alter session set events 10046 trace…...
微软自带浏览器Edge,无法关闭“保存历史记录网站的屏幕截图”解决方案
微软自带浏览器Edge,无法关闭“保存历史记录网站的屏幕截图”解决方案 吐槽1:Windows自带的Chrome内核版本的浏览器Microsofg Edge刚发布时可谓一股清流,启动速度快,占用内存较小,相信很多人也开始抛弃正代Chrome&…...
讲座 | 颠覆传统摄像方式乃至计算机视觉的“脉冲视觉”
传统相机拍摄视频时其实是以一定帧率进行采样,视频其实还是一串图片的集合,因此低帧率时会觉得视频卡,拍摄高速运动物体时会有运动模糊等等问题。然而你能想象这一切都可以被“脉冲视觉”这一前沿技术改变吗? 今天下午听了北京大学…...
uniGUI学习之UniHTMLMemo1富文本编辑器
1]系统自带的富文本编辑器 2]jQueryBootstarp富文本编辑器插件summernote.js 1]系统自带的富文本编辑器 1、末尾增加<p> 2、增加字体 3、解决滚屏问题 4、输入长度限制问题 5、显示 并 编辑 HTML源代码(主要是图片处理) 1、末尾增加<p> UniHTMLMemo1.Lines…...
详细教程 - 从零开发 鸿蒙harmonyOS应用 第四节 (鸿蒙Stage模型 登录页面 ArkTS版 推荐使用)
在鸿蒙OS中,Ability是应用程序提供的抽象功能,可以理解为一种功能。在应用程序中,一个页面即一种能力,如登录页面,即具有登录功能的能力。以下是对鸿蒙新建项目的登录代码功能的详细解读和工作流程的描述: …...
uniapp怎么实现授权登录
在Uniapp中实现授权登录通常涉及以下几个步骤: 创建登录按钮:在页面中创建一个按钮,用于触发登录操作。 获取用户授权:当用户点击登录按钮时,调用uni.login或uni.getUserInfo等API获取用户授权。 处理授权回调&#…...
从零开始:前端架构师的基础建设和架构设计之路
文章目录 一、引言二、前端架构师的职责三、基础建设四、架构设计思想五、总结《前端架构师:基础建设与架构设计思想》编辑推荐内容简介作者简介目录获取方式 一、引言 在现代软件开发中,前端开发已经成为了一个不可或缺的部分。随着互联网的普及和移动…...
椋鸟C语言笔记#26:数据在内存中的存储(大小端字节序)、浮点数的存储(IEEE754)
萌新的学习笔记,写错了恳请斧正。 目录 大小端字节序 什么是大小端 写一个判断大小端的程序 浮点数在内存中的存储(IEEE 754规则) 引入 存储规则解释 读取规则解释 1.阶码不全为0或全为1(规格化数) 2.阶码全为…...
设计模式——组合模式(结构型)
引言 组合模式是一种结构型设计模式, 你可以使用它将对象组合成树状结构, 并且能像使用独立对象一样使用它们。 问题 如果应用的核心模型能用树状结构表示, 在应用中使用组合模式才有价值。 例如, 你有两类对象: …...
鸿蒙小车之多任务调度实验
说到鸿蒙我们都会想到华为mate60:遥遥领先!我们一直领先! 我们这个小车也是采用的是鸿蒙操作系统,学习鸿蒙小车,让你遥遥领先于你的同学。 文章目录 前言一、什么是任务?为什么要有任务二、任务的状态三、任…...
【报错栏】(vue)Module not found: Error: Can‘t resolve ‘element-ui‘ in xxx
Module not found: Error: Cant resolve element-ui in xxx 报错原因是: 未安装 element-ui 依赖 解决: npm install element-ui 运行...
seaborn库图形进行数据分析(基于tips数据集)
Seaborn 是一个基于 matplotlib 的数据可视化库,可以用来绘制各种统计图表,包括散点图、条形图、折线图、箱线图等。Seaborn 提供了一些用于美化图表的默认样式和颜色主题,使得生成的图表更具有吸引力。下面是一些 Seaborn 库的常用功能和用法…...
AC843. n皇后问题--60
我们只需要把蓝色的往上移动就行了 if(!col[i][j]&&!dg[ui]&&!udg[])//1y(i)向下,x(u)向右为正。yxb的by-x一定>0,y-xb的bxy可能>0,这个不考虑,只看-bxy....
Js WebSocket类,收发Json,带心跳,断线重连
如题 心跳:4秒发一次 断线:2秒后自动重连 收发:发送和返回json,处理粘包断包等情况,json字符串最大长度9999 缓存:未连接时,自动缓存100个包,当连接时会自动发出 JS代码 var MyWeb…...
VBA技术资料MF96:单字段多条件高级筛选
我给VBA的定义:VBA是个人小型自动化处理的有效工具。利用好了,可以大大提高自己的工作效率,而且可以提高数据的准确度。我的教程一共九套,分为初级、中级、高级三大部分。是对VBA的系统讲解,从简单的入门,到…...
电子取证中Chrome各版本解密Cookies、LoginData账号密码、历史记录
文章目录 1.前置知识点2.对于80.X以前版本的解密拿masterkey的几种方法方法一 直接在目标机器运行Mimikatz提取方法二 转储lsass.exe 进程从内存提取masterkey方法三 导出SAM注册表 提取user hash 解密masterkey文件(有点麻烦不太推荐)方法四 已知用户密…...
Axure元件基本介绍进阶
Axure元件基本介绍进阶 1.Axure元件基本介绍1.在 Axure 中,元件是构建原型的基本构成单元,能够帮助设计师快速创建、重复使用和管理设计元素。以下是 Axure 中元件的基本介绍:1.基本元件: 2.基本元件的使用一.【举例说明】积木&am…...
安卓11添加切换以太网动态静态方法
客户要在app中自由切换动态,静态方法,直接把系统jar-api给他搞了半天搞不定,只有在系统里给他实现一个接口,方法如下: Index: packages/apps/Settings/AndroidManifest.xml--- packages/apps/Settings/AndroidManifes…...
PyFluent:如何用Python代码将CFD仿真效率提升10倍?
PyFluent:如何用Python代码将CFD仿真效率提升10倍? 【免费下载链接】pyfluent Pythonic interface to Ansys Fluent 项目地址: https://gitcode.com/gh_mirrors/pyf/pyfluent PyFluent作为Ansys Fluent的Python原生接口,正在彻底改变C…...
别再瞎勾选了!SuperMap iDesktop切MVT矢量瓦片时,‘分离数据与风格’到底怎么选?
MVT矢量瓦片生产中的关键决策:数据与风格分离的深度解析 当你在SuperMap iDesktop中准备生成MVT矢量瓦片时,那个看似简单的"分离数据与风格"复选框背后,隐藏着一系列影响深远的架构决策。这个选择不仅关系到瓦片文件的结构…...
Nodejs开发者如何通过Taotoken快速集成大模型到现有项目
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 Node.js开发者如何通过Taotoken快速集成大模型到现有项目 对于正在使用Node.js构建后端服务或全栈应用的开发者来说,集…...
kkFileView容器网络性能优化:基于SR-IOV的硬件加速终极指南
kkFileView容器网络性能优化:基于SR-IOV的硬件加速终极指南 【免费下载链接】kkFileView Universal File Online Preview Project based on Spring-Boot 项目地址: https://gitcode.com/GitHub_Trending/kk/kkFileView 在现代云原生应用中,容器化…...
Cadence SPB17.4批量改封装太慢?巧用CIS数据库Key值,效率翻倍不是梦
Cadence SPB17.4封装批量修改效率革命:CIS数据库Key值深度应用指南 硬件工程师的日常工作中,封装管理往往是耗时又容易出错的环节。当你在Cadence SPB17.4中面对数百个需要同步更新的元件封装时,传统的手工修改方式不仅效率低下,还…...
“同学家住别墅,咱们穷吗?”:最好的家产,是睡个好觉
有一天傍晚,刚把小儿子从学校接回来,这小子书包都没来得及放下,就给我抛出了一个灵魂拷问。“爸,今天听同学说,他们家换了大别墅,上下三层还有专门看电影的房间。”他顿了顿,眼神里带着一种真诚…...
【花雕学编程】Arduino BLDC 之基于MimiClaw+ ESP32S3的智能跟随机器人
导语 该拓展思路以 ESP32‑S3MimiClawArduino BLDC 为核心,融合嵌入式 AI 无刷动力 多模态感知,具备全向机动、地形适应、智能跟随、低功耗长续航等优势,覆盖消费随行、工业协同、特种科考、教育科研等场景。 一、系统概述 Arduino BLDC …...
从医院PACS到你的电脑:手把手教你用免费工具查看和转换DCM文件(Windows/Mac)
从医院PACS到个人电脑:零基础掌握DICOM影像查看与转换全流程 第一次从医院PACS系统导出DICOM文件时,那种"双击打不开、专业软件不会用"的挫败感我至今记忆犹新。作为医学影像的黄金标准格式,DCM文件包含着远比普通图片丰富的诊断信…...
2026年主流进口工业连接器品牌探讨
在工业 4.0 深化落地与能源转型加速推进的背景下,工业连接器已成为保障工业设备、产线稳定运行的核心基础部件,其可靠性直接影响生产效率与运维成本。依托成熟的技术积淀、严格的品控体系与丰富的场景适配经验,进口工业连接器品牌在高端装备制造、新能源、工业自动化等领域仍占…...
Timepix4混合像素探测器系统与DataPix4框架解析
1. Timepix4混合像素探测器系统概述Timepix4作为CERN Medipix合作组研发的第四代混合像素探测器ASIC,代表了当前粒子探测领域的最前沿技术。这款芯片采用65nm CMOS工艺制造,核心是一个由448512个像素组成的矩阵,每个像素尺寸为5555μm&#x…...
