当前位置: 首页 > news >正文

代码随想录刷题day32丨动态规划理论基础,509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯

代码随想录刷题day32丨动态规划理论基础,509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯

1.动态规划理论基础

  • 动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。

  • 动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的

  • 动态规划的解题步骤(动规五步曲)
    1. 确定dp数组(dp table)以及下标的含义
    2. 确定递推公式
    3. dp数组如何初始化
    4. 确定遍历顺序
    5. 举例推导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],我们来推导一下,当N10的时候,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丨动态规划理论基础&#xff0c;509. 斐波那契数&#xff0c; 70. 爬楼梯&#xff0c; 746. 使用最小花费爬楼梯 1.动态规划理论基础 动态规划&#xff0c;英文&#xff1a;Dynamic Programming&#xff0c;简称DP&#xff0c;如果某一问题有很多重叠子问题…...

为什么矩阵特征值之和等于主对角线元素之和,特征值乘积等于行列式值

首先给出特征值和特征向量的定义。 设A是n阶矩阵&#xff0c;如果数λ和n维非零向量x使关系式 Axλx &#xff08;1&#xff09; 成…...

学生学籍管理系统可行性分析报告

引言 一、编写目的 随着科学技术的不断提高,计算机科学日渐成熟,其强大的功能已为人们深刻认识,它已进入人类社会的各个领域并发挥着越来越重要的作用。而学籍管理系统软件&#xff0c;可广泛应用于全日制大、中小学及其他各类学校&#xff0c;系统涵盖了小学、初中、高中学籍…...

C#排序算法新境界:深度剖析与高效实现基数排序

基数排序&#xff08;Radix Sort&#xff09;是一种非比较型整数排序算法&#xff0c;其原理是将整数按位数切割成不同的数字&#xff0c;然后按每个位数进行比较。具体来说&#xff0c;基数排序有两种方法&#xff1a; 最低位优先&#xff08;LSD, Least Significant Digit f…...

玩机搞机-----如何简单的使用ADB指令来卸载和冻结系统应用 无需root权限 详细操作图示教程

同类博文&#xff1a; 玩机搞机---卸载内置软件 无root权限卸载不需要的软件 安全卸载_无需root卸载彻底内置软件-CSDN博客 在很多时候我们需要卸载一些系统级的app。但如果直接手机端进行卸载的话。是无法正常卸载的。其实我们可以通过有些成品工具或者完全靠ADB指令来进行卸…...

如何通过 Apache Camel 将数据导入 Elasticsearch

作者&#xff1a;来自 Elastic Andre Luiz 使用 Apache Camel 将数据提取到 Elasticsearch 的过程将搜索引擎的稳健性与集成框架的灵活性相结合。在本文中&#xff0c;我们将探讨 Apache Camel 如何简化和优化将数据提取到 Elasticsearch。为了说明此功能&#xff0c;我们将实…...

打造民国风格炫酷个人网页:用HTML和CSS3传递民国风韵

附源码&#xff01;&#xff01;&#xff01; 感谢支持 小弟不断创作网站demo感兴趣的可以关注支持一下 对了 俺在结尾带上了自己用的 背景 大家可以尝试换一下效果更好哦~~~ 如何创建一个民国风格的炫酷网页 在这篇博客中&#xff0c;我们将展示如何制作一个结合民国风格和…...

豆包MarsCode编程助手:产品功能解析与应用场景探索!

随着现代技术的不断进化升级&#xff0c;人工智能正在逐步改变着我们的日常工作方式。特别是对于复杂的项目&#xff0c;代码编写、优化、调试、测试等环节充满挑战。为了简化这些环节、提高开发效率&#xff0c;许多智能编程工具应运而生&#xff0c;豆包MarsCode 编程助手就是…...

爬虫全网抓取

爬虫全网抓取是指利用网络爬虫技术&#xff0c;通过自动化的方式遍历互联网上各个网站、论坛、博客等&#xff0c;从这些网页中提取所需的数据。它通常涉及以下几个步骤&#xff1a; 目标设定&#xff1a;确定要抓取哪些类型的网页内容&#xff0c;比如新闻、商品信息、用户评论…...

【计算机组成原理】详细解读带符号整数在计算机中的运算

有符号整数的运算 导读一、补码的优势二、补码的加法运算三、补码的减法运算四、原码、反码、补码的特性结语 导读 大家好&#xff0c;很高兴又和大家见面啦&#xff01;&#xff01;&#xff01; 经过前面的介绍&#xff0c;我们已经初步认识了有符号整数的三种表示形式&…...

vue3常见的bug 修复bug

Vue 3 作为 Vue.js 的最新版本&#xff0c;在性能、开发体验以及代码可维护性等方面带来了显著的提升。然而&#xff0c;就像任何软件框架一样&#xff0c;Vue 3 在使用过程中也可能遇到一些典型的bug或问题。以下是一些可能遇到的典型问题&#xff1a; 响应式系统相关的问题&…...

C++课程笔记 类和对象

类概念 结构体&#xff1a;只要属性 类&#xff1a;有属性也有方法 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灵感爆发

文章目录 &#x1f34a;AI内容创作的精髓&#xff1a;提示词Prompt1 什么是提示词工程?1.1 提示词是如何影响AI的输出结果?1.2 提示词的原理是什么1.3 提示词工程师的前景1.4 谁能成为提示词工程师&#xff1f;1.5 提示词的未来前景 2 提示词的基本书写技巧3 常见的提示词框架…...

一码空传临时网盘PHP源码,支持提取码功能

源码介绍 一码空传临时网盘源码V2.0免费授权&#xff0c;该源码提供了一个简单易用的无数据库版临时网盘解决方案。前端采用了layui开发框架&#xff0c;后端使用原生PHP编写&#xff0c;没有引入任何开发框架&#xff0c;保持了代码的简洁和高效。 这个程序使用了一个无数据…...

自然语言处理实战项目

自然语言处理实战项目 自然语言处理&#xff08;NLP, Natural Language Processing&#xff09;是人工智能的重要分支之一&#xff0c;致力于让计算机理解、生成并与人类进行语言交互。随着深度学习、神经网络和大数据的发展&#xff0c;NLP技术在近年来取得了飞跃性的进展&am…...

人工智能物联网的去中心化和分布式学习:全面综述、新兴挑战和机遇

这篇论文的标题是《Decentralized and Distributed Learning for AIoT: A Comprehensive Review, Emerging Challenges, and Opportunities》&#xff0c;作者是Hanyue Xu, Kah Phooi Seng, Li Minn Ang, 和 Jeremy Smith。论文发表在IEEE Access期刊上&#xff0c;接收日期为2…...

滑动窗口算法—最小覆盖子串

题目 ”最小覆盖子串“问题&#xff0c;难度为Hard&#xff0c;题目如下&#xff1a; 给你两个字符串 S 和 T&#xff0c;请你在 S 中找到包含 T 中全部字母的最短子串。如果 S 中没有这样一个子串&#xff0c;则算法返回空串&#xff0c;如果存在这样一个子串&#xff0c;则可…...

应用案例|开源 PolarDB-X 在互联网安全场景的应用实践

背景介绍 中盾数科集团始创于2012年&#xff0c;是由网络安全服务而发展起来的科技型、多元化的企业集团。旗下包括网络安全服务、信创一体化服务、箱式液冷、区块链、位置服务、视觉服务等六大板块&#xff0c;业务覆盖湖南、甘肃、贵州等多个省份。 业务挑战 中盾集团基于A…...

【大数据】MapReduce的“内存增强版”——Spark

【大数据】MapReduce的“内存增强版”——Spark 文章脉络 Spark架构 Spark-core SparkConf 和 SparkContext RDD Spark集群 Spark-sql 在大数据时代&#xff0c;数据处理和分析成为企业竞争的重要手段。Hadoop作为大数据处理的基石&#xff0c;其核心组件MapReduce在众多…...

o1模型:引领AI技术在STEM领域的突破与应用

o1模型是OpenAI最新推出的大型语言模型&#xff0c;它在多个领域展现出了卓越的能力&#xff0c;被认为是AI技术发展的一个重要里程碑。以下是对o1模型的详细介绍和分析&#xff1a; o1模型的简介和性能评估 o1模型在物理、化学、生物学等领域的基准任务上达到了博士生水平&…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...