代码随想录刷题day32丨动态规划理论基础,509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯
代码随想录刷题day32丨动态规划理论基础,509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯
1.动态规划理论基础
-
动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。
-
动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的
-
动态规划的解题步骤(动规五步曲)
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
-
为什么要先确定递推公式,然后在考虑初始化呢?
- 因为一些情况是递推公式决定了dp数组要如何初始化!
-
代码出错找问题的最好方式就是把dp数组打印出来,看看究竟是不是按照自己思路推导的!
-
做动规的题目,写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍,心中有数,确定最后推出的是想要的结果。
然后再写代码,如果代码没通过就打印dp数组,看看是不是和自己预先推导的哪里不一样。
如果打印出来和自己预先模拟推导是一样的,那么就是自己的递归公式、初始化或者遍历顺序有问题了。
如果和自己预先模拟推导的不一样,那么就是代码实现细节有问题。
2.题目
2.1斐波那契数
- 题目链接:509. 斐波那契数 - 力扣(LeetCode)

-
视频讲解:手把手带你入门动态规划 | LeetCode:509.斐波那契数_哔哩哔哩_bilibili
-
文档讲解:https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html
-
解题思路:动态规划
-
确定dp数组以及下标的含义
dp[i]的定义为:第i个数的斐波那契数值是dp[i] -
确定递推公式
dp[i] = dp[i - 1] + dp[i - 2] -
dp数组如何初始化
dp[0] = 0; dp[1] = 1; -
确定遍历顺序
从前到后遍历 -
举例推导dp数组
按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2],我们来推导一下,当N为10的时候,dp数组应该是如下的数列:0 1 1 2 3 5 8 13 21 34 55如果代码写出来,发现结果不对,就把dp数组打印出来看看和我们推导的数列是不是一致的。
-
-
代码:
//dp解法 //时间复杂度:O(n) //空间复杂度:O(n) class Solution {public int fib(int n) {if(n <= 1){return n;}int[] dp = new int[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];} }//压缩版dp,只需要维护两个数值就可以了,不需要记录整个序列 //时间复杂度:O(n) //空间复杂度:O(1) class Solution {public int fib(int n) {if(n <= 1){return n;}int a = 0;int b = 1;int c = 0;for(int i = 2;i <= n;i++){c = a + b;a = b;b = c;}return c;} }//递归解法 //时间复杂度:O(2^n) //空间复杂度:O(n),算上了编程语言中实现递归的系统栈所占空间 class Solution {public int fib(int n) { if(n <= 1){return n;}return fib(n - 1) + fib(n - 2);} } -
总结:
- 动规五部曲方法很重要!
2.2爬楼梯
-
题目链接:70. 爬楼梯 - 力扣(LeetCode)

-
视频讲解:带你学透动态规划-爬楼梯(对应力扣70.爬楼梯)| 动态规划经典入门题目_哔哩哔哩_bilibili
-
文档讲解:https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html
-
解题思路:动态规划
-
确定dp数组以及下标的含义
dp[i]: 爬到第i层楼梯,有dp[i]种方法 -
确定递推公式
dp[i] = dp[i - 1] + dp[i - 2] -
dp数组如何初始化
dp[1] = 1,dp[2] = 2 -
确定遍历顺序
从前向后遍历 -
举例推导dp数组
举例当n为5的时候,dp数组应该是:
-
-
代码:
class Solution {public int climbStairs(int n) {if(n == 1){return 1;}int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;for(int i = 3;i <= n;i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];} }为什么需要特殊处理
n = 1?- 如果
n = 1,代码只需要直接返回 1,因为到达第 1 阶只有一种方法:一步爬到。 - 而当
n = 1时,你不应该初始化dp[2] = 2;,因为数组中只有dp[0]和dp[1],dp[2]并不存在,试图访问它会引发数组越界。
- 如果
-
总结:
- 题目中要求的每次可以爬1或者2个台阶,也就是说,最终到达n阶台阶有两种方式,一个是爬1阶台阶到达(对应的是从n-1阶台阶开始),那么另一个就是爬2阶台阶到达(对应的是从n-2阶台阶开始爬),而爬n-1阶和n-2阶台阶的方法有dp【n-1】,dp【n-2】个。所以最终爬n阶台阶的方法种类就是dp【n-1】+dp【n-2】。其实也对应了卡哥所说的从n-1和n-2阶爬上去,探究的是几种走法,而不是几步。
- 没有讨论dp[0]应该是什么,因为dp[0]在本题没有意义!
2.3使用最小花费爬楼梯
-
题目链接:746. 使用最小花费爬楼梯 - 力扣(LeetCode)

-
视频讲解:动态规划开更了!| LeetCode:746. 使用最小花费爬楼梯_哔哩哔哩_bilibili
-
文档讲解:https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html
-
解题思路:动态规划
-
图示

-
确定dp数组以及下标的含义
dp[i]的定义:到达第i台阶所花费的最少体力为dp[i] -
确定递推公式
可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]。dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢?一定是选最小的,所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); -
dp数组如何初始化
dp[0] = 0;//到达 第 0 个台阶是不花费的,但从 第0 个台阶 往上跳的话,需要花费 cost[0]。 dp[1] = 0;//到达 第 1 个台阶是不花费的,但从 第1 个台阶 往上跳的话,需要花费 cost[1]。 -
确定遍历顺序
从前到后遍历 -
举例推导dp数组
拿示例2:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,来模拟一下dp数组的状态变化,如下:
-
-
代码:
class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp = new int[cost.length + 1];// 从下标为 0 或下标为 1 的台阶开始,因此支付费用为0dp[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];} } -
总结:
- 理解自己定义的dp[i] 至关重要
- 初始化的时候要结合实际情况
- 注意数组越界问题
相关文章:
代码随想录刷题day32丨动态规划理论基础,509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯
代码随想录刷题day32丨动态规划理论基础,509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯 1.动态规划理论基础 动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题…...
为什么矩阵特征值之和等于主对角线元素之和,特征值乘积等于行列式值
首先给出特征值和特征向量的定义。 设A是n阶矩阵,如果数λ和n维非零向量x使关系式 Axλx (1) 成…...
学生学籍管理系统可行性分析报告
引言 一、编写目的 随着科学技术的不断提高,计算机科学日渐成熟,其强大的功能已为人们深刻认识,它已进入人类社会的各个领域并发挥着越来越重要的作用。而学籍管理系统软件,可广泛应用于全日制大、中小学及其他各类学校,系统涵盖了小学、初中、高中学籍…...
C#排序算法新境界:深度剖析与高效实现基数排序
基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数进行比较。具体来说,基数排序有两种方法: 最低位优先(LSD, Least Significant Digit f…...
玩机搞机-----如何简单的使用ADB指令来卸载和冻结系统应用 无需root权限 详细操作图示教程
同类博文: 玩机搞机---卸载内置软件 无root权限卸载不需要的软件 安全卸载_无需root卸载彻底内置软件-CSDN博客 在很多时候我们需要卸载一些系统级的app。但如果直接手机端进行卸载的话。是无法正常卸载的。其实我们可以通过有些成品工具或者完全靠ADB指令来进行卸…...
如何通过 Apache Camel 将数据导入 Elasticsearch
作者:来自 Elastic Andre Luiz 使用 Apache Camel 将数据提取到 Elasticsearch 的过程将搜索引擎的稳健性与集成框架的灵活性相结合。在本文中,我们将探讨 Apache Camel 如何简化和优化将数据提取到 Elasticsearch。为了说明此功能,我们将实…...
打造民国风格炫酷个人网页:用HTML和CSS3传递民国风韵
附源码!!! 感谢支持 小弟不断创作网站demo感兴趣的可以关注支持一下 对了 俺在结尾带上了自己用的 背景 大家可以尝试换一下效果更好哦~~~ 如何创建一个民国风格的炫酷网页 在这篇博客中,我们将展示如何制作一个结合民国风格和…...
豆包MarsCode编程助手:产品功能解析与应用场景探索!
随着现代技术的不断进化升级,人工智能正在逐步改变着我们的日常工作方式。特别是对于复杂的项目,代码编写、优化、调试、测试等环节充满挑战。为了简化这些环节、提高开发效率,许多智能编程工具应运而生,豆包MarsCode 编程助手就是…...
爬虫全网抓取
爬虫全网抓取是指利用网络爬虫技术,通过自动化的方式遍历互联网上各个网站、论坛、博客等,从这些网页中提取所需的数据。它通常涉及以下几个步骤: 目标设定:确定要抓取哪些类型的网页内容,比如新闻、商品信息、用户评论…...
【计算机组成原理】详细解读带符号整数在计算机中的运算
有符号整数的运算 导读一、补码的优势二、补码的加法运算三、补码的减法运算四、原码、反码、补码的特性结语 导读 大家好,很高兴又和大家见面啦!!! 经过前面的介绍,我们已经初步认识了有符号整数的三种表示形式&…...
vue3常见的bug 修复bug
Vue 3 作为 Vue.js 的最新版本,在性能、开发体验以及代码可维护性等方面带来了显著的提升。然而,就像任何软件框架一样,Vue 3 在使用过程中也可能遇到一些典型的bug或问题。以下是一些可能遇到的典型问题: 响应式系统相关的问题&…...
C++课程笔记 类和对象
类概念 结构体:只要属性 类:有属性也有方法 c可以省略struct c不行 #include<iostream> using namespace std;typedef struct queue1 {int a;queue1 q() {queue1 q(2);return q;};queue1(){}queue1(int qa){a qa;} }q1; int main() {queue1 Q1;…...
提问即创作:用Prompt提示词引领AI灵感爆发
文章目录 🍊AI内容创作的精髓:提示词Prompt1 什么是提示词工程?1.1 提示词是如何影响AI的输出结果?1.2 提示词的原理是什么1.3 提示词工程师的前景1.4 谁能成为提示词工程师?1.5 提示词的未来前景 2 提示词的基本书写技巧3 常见的提示词框架…...
一码空传临时网盘PHP源码,支持提取码功能
源码介绍 一码空传临时网盘源码V2.0免费授权,该源码提供了一个简单易用的无数据库版临时网盘解决方案。前端采用了layui开发框架,后端使用原生PHP编写,没有引入任何开发框架,保持了代码的简洁和高效。 这个程序使用了一个无数据…...
自然语言处理实战项目
自然语言处理实战项目 自然语言处理(NLP, Natural Language Processing)是人工智能的重要分支之一,致力于让计算机理解、生成并与人类进行语言交互。随着深度学习、神经网络和大数据的发展,NLP技术在近年来取得了飞跃性的进展&am…...
人工智能物联网的去中心化和分布式学习:全面综述、新兴挑战和机遇
这篇论文的标题是《Decentralized and Distributed Learning for AIoT: A Comprehensive Review, Emerging Challenges, and Opportunities》,作者是Hanyue Xu, Kah Phooi Seng, Li Minn Ang, 和 Jeremy Smith。论文发表在IEEE Access期刊上,接收日期为2…...
滑动窗口算法—最小覆盖子串
题目 ”最小覆盖子串“问题,难度为Hard,题目如下: 给你两个字符串 S 和 T,请你在 S 中找到包含 T 中全部字母的最短子串。如果 S 中没有这样一个子串,则算法返回空串,如果存在这样一个子串,则可…...
应用案例|开源 PolarDB-X 在互联网安全场景的应用实践
背景介绍 中盾数科集团始创于2012年,是由网络安全服务而发展起来的科技型、多元化的企业集团。旗下包括网络安全服务、信创一体化服务、箱式液冷、区块链、位置服务、视觉服务等六大板块,业务覆盖湖南、甘肃、贵州等多个省份。 业务挑战 中盾集团基于A…...
【大数据】MapReduce的“内存增强版”——Spark
【大数据】MapReduce的“内存增强版”——Spark 文章脉络 Spark架构 Spark-core SparkConf 和 SparkContext RDD Spark集群 Spark-sql 在大数据时代,数据处理和分析成为企业竞争的重要手段。Hadoop作为大数据处理的基石,其核心组件MapReduce在众多…...
o1模型:引领AI技术在STEM领域的突破与应用
o1模型是OpenAI最新推出的大型语言模型,它在多个领域展现出了卓越的能力,被认为是AI技术发展的一个重要里程碑。以下是对o1模型的详细介绍和分析: o1模型的简介和性能评估 o1模型在物理、化学、生物学等领域的基准任务上达到了博士生水平&…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
Linux安全加固:从攻防视角构建系统免疫
Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...
前端调试HTTP状态码
1xx(信息类状态码) 这类状态码表示临时响应,需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分,客户端应继续发送剩余部分。 2xx(成功类状态码) 表示请求已成功被服务器接收、理解并处…...
