代码随想录刷题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] 至关重要
    • 初始化的时候要结合实际情况
    • 注意数组越界问题

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/423568.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

QT 串口上位机读卡显示

目录 一. QT创建工程 二. 软件更换图标 三. QT打包 一. QT创建工程 文件新建&#xff0c;选择创建一个桌面QT。 重命名RFID,并选择工程保存路径 RFID.pro QT core gui serialport #串行串口greaterThan(QT_MAJOR_VERSION, 4): QT widgetsTARGET RFID TE…

GD - GDLink的接口引脚杜邦线接触不好,还是自己做一个转接头好些

文章目录 GD - GDLink的接口引脚杜邦线接触不好&#xff0c;还是自己做一个转接头好些概述笔记转接头使用时的连接关系转接头弄个壳子好些在转接头上&#xff0c;将线序转为自己板子SWD的防呆线序 转接头的2x5P线序和看到的GD-LINK2x5P接口相反END GD - GDLink的接口引脚杜邦线…

Xcode报错:Return from initializer without initializing all stored properties

Xcode报错&#xff1a;Return from initializer without initializing all stored properties,self used before all stored properties are initialized 我们自定义 init 方法&#xff0c;在 init 中直接赋值 Binding 会失败,但是直接赋值给Binding类型的变量却正常&#xff…

94 、k8s之rbac

一、rbac----安全机制 赋权机制 集群是按照用户名进行登录&#xff0c;按照项目名称进行命名空间的分类。 配电云主站------62天 8个人 高温补贴 一主2从 user pdyzz pdyzz -n pdyzz 资源空间 pod数量 1.1、k8s的安全机制&#xff1a; apiserver------>集群内和外…

HTML+CSS - 网页布局之网格布局

1. dispaly设置 display是 CSS 中用于设置元素的显示方式的属性。它决定了元素如何被渲染到页面上。不同的display值会改变元素的显示行为&#xff0c;包括布局、排版以及对其他元素的影响。 其中网格容器是最常用的几种方式之一&#xff0c;在文档中创建类似于网格的效果&…

【Go】Go语言中延迟函数、函数数据的类型、匿名函数、闭包等高阶函数用法与应用实战

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…

Mysql | 知识 | 理解是怎么加锁的

文章目录 一、怎么加行级锁的&#xff1f;二、唯一索引加锁2.1 唯一索引等值查询1、记录存在的情况2、记录不存在的情况 2.2 唯一索引范围查询a. 针对「大于」的范围查询b. 针对「大于等于」的范围查询的情况。c. 「小于」范围查询&#xff0c;记录「不存在」表中的情况d. 「小…

音乐革命:揭秘树莓派如何重塑 Korg 合成器的未来

采用快速紧凑的 Raspberry Pi 计算模块3&#xff08;Raspberry Pi Compute Module 3&#xff09;的简易设置&#xff0c;为Korg备受推崇的高端乐器提供了一种经济高效的解决方案。 解决方案&#xff1a;Compute Module 3 企业规模&#xff1a;大型企业 行业&#xff1a;音乐…

uniapp小程序,使用腾讯地图获取定位

本篇文章分享一下在实际开发小程序时遇到的需要获取用户当前位置的问题&#xff0c;在小程序开发过程中经常使用到获取定位功能。uniapp官方也提供了相应的API供我们使用。 官网地址&#xff1a;uni.getLocation(OBJECT)) 官网获取位置的详细介绍这里就不再讲述了&#xff0c;大…

【LeetCode】每日一题 2024_9_14 从字符串中移除星号(模拟)

前言 每天和你一起刷 LeetCode 每日一题~ LeetCode 启动&#xff01; 今天的题目曾经的我做过了 . . . 又是复习的一天 题目&#xff1a;从字符串中移除星号 代码与解题思路 func removeStars(s string) string {// 本题的核心&#xff1a;生成的输入保证总是可以执行题面中…

大数据-136 - ClickHouse 集群 表引擎详解1 - 日志、Log、Memory、Merge

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff08;已更完&#xff09;HDFS&#xff08;已更完&#xff09;MapReduce&#xff08;已更完&am…

【绿盟科技盟管家-注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…

秒懂:父子进程与bash(命令行参数)的关系

情景解析&#xff1a; 执行以下代码&#xff1a; #include<string.h> #include<unistd.h> int g_val 100000;int main() {int key7;printf("I am father process, pid: %d, ppid: %d, g_val: %d\n", getpid(), getppid(), g_val);sleep(5);pid_t id f…

现代 Web 开发全攻略:Node.js、npm、Webpack、Vue.js 和 Element-UI 的实战指南

现代 Web 开发全攻略&#xff1a;Node.js、npm、Webpack、Vue.js 和 Element-UI 的实战指南 一 . Node.js1.1 什么是 Node.js ?1.2 Node.js 的安装1.3 快速入门1.3.1 控制台输出1.3.2 使用函数1.3.3 模块化编程 二 . npm 包管理器2.1 什么是 npm ?2.2 npm 命令2.2.1 初始化工…

护眼灯品牌排行第一名出炉!盘点2024年世界公认十大护眼灯

中国拥有全球最多的近视人口&#xff0c;我国学生的近视发病率位居世界第二&#xff0c;人数更是居于首位。如今&#xff0c;越来越多的孩子出现近视现象&#xff0c;许多家长认为这是由于繁重的课业和不健康的用眼习惯所致&#xff0c;但实际上&#xff0c;他们往往忽视了一个…

数据分析-前期数据处理

今天找到一份关于医学体检的数据&#xff0c;在数据分析前期工作需要对数据做处理&#xff0c;在这里我们对原始数据做一些处理&#xff0c;将数据处理为可分析的标准数据。下一篇文章做数据的分析。数据想要获取的话可以到我的资源下载。1 数据读取 import pandas as pd data…

SQL Server详细使用教程(包含启动SQL server服务、建立数据库、建表的详细操作) 非常适合初学者

文章目录 目录 前言 一、启动SQL server服务的三种方法 1.不启动SQL server服务的影响 2.方法一&#xff1a;利用cmd启动SQL server服务 3.方法二&#xff1a;利用SQL Server配置管理器启动SQL server服务 4.方法三&#xff1a;在服务管理器中启动SQL server服务 二、建立数据库…

震撼!AI实时生成游戏,每秒20帧,谷歌扩散模型最新突破一夜爆火,附论文介绍和GitHub代码

震撼&#xff01;AI实时生成游戏&#xff0c;每秒20帧&#xff0c;谷歌扩散模型最新突破一夜爆火&#xff0c;附论文介绍和GitHub代码。 “比Sora还震撼”&#xff0c;AI可以实时生成游戏了&#xff01; 谷歌DeepMind打造出了首个完全AI驱动的实时游戏引擎——GameNGen。 在单…

SpringBoot集成MyBatis-PlusDruid

目录 MyBatis-Plus简介 实例演示 创建Springboot项目 初始化Springboot项目 添加关键依赖 application.properties添加相关配置 启动类 编写实体类 编写mapper接口 条件构造器 分页插件 自定义 SQL 映射 MyBatis-Plus简介 MyBatis-Plus简介‌MyBatis-Plus‌&…

RDD2022 道路瑕疵检测数据集

RDD2022 道路瑕疵数据集 txt标签或者xml标签 一共23767张图片 D00 D01 D20 D40四类 D00纵向裂缝 D10横向裂缝 D20网状裂缝 D40坑洞。 RDD2022 道路瑕疵检测数据集介绍 数据集概述 RDD2022&#xff08;Road Defect Detection 2022&#xff09;是一个专门用于道路瑕疵检测的数…