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

网站建设如何跑单子/百度快速排名技术培训

网站建设如何跑单子,百度快速排名技术培训,企业名录黄页大全,网络市场调研的方法动态规划理论基础 动态规划刷题大纲 什么是动态规划 动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。 所以动态规划中每一个状态一定是由上一个状态推导出来的&a…

动态规划理论基础

动态规划刷题大纲

什么是动态规划

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

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

在关于贪心算法,你该了解这些! (opens new window)中卡哥举了一个背包问题的例子。

例如:有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

动态规划中 dp[j] 是由 dp[j-weight[i]] 推导出来的,然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢,每次拿物品选一个最大的或者最小的就完事了,和上一个状态没有关系。

所以贪心解决不了动态规划的问题。

不用死扣动规和贪心的理论区别,慢慢的就知道了

动规是由前一个状态推导出来的,而贪心是局部直接选最优的

动态规划的解题步骤

状态转移公式(递推公式)是很重要,但动规不仅仅只有递推公式。

对于动态规划问题,卡哥将拆解为如下五步曲,这五步都搞清楚了,才能说把动态规划真的掌握了!

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

为什么要先确定递推公式,然后在考虑初始化呢?

因为一些情况是递推公式决定了dp数组要如何初始化!

动态规划应该如何debug

找问题的最好方式就是把dp数组打印出来,看看究竟是不是按照自己思路推导的!

做动规的题目,写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍,心中有数,确定最后推出的是想要的结果

然后再写代码,如果代码没通过就打印dp数组,看看是不是和自己预先推导的哪里不一样。

如果打印出来和自己预先模拟推导是一样的,那么就是自己的递归公式、初始化或者遍历顺序有问题了。

如果和自己预先模拟推导的不一样,那么就是代码实现细节有问题。

这样才是一个完整的思考过程,而不是一旦代码出问题,就毫无头绪的东改改西改改,最后过不了,或者说是稀里糊涂的过了

这也是卡哥为什么在动规五步曲里强调推导dp数组的重要性。

举个例子哈:在「代码随想录」刷题小分队微信群里,一些录友可能代码通过不了,会把代码抛到讨论群里问:我这里代码都已经和题解一模一样了,为什么通过不了呢?

发出这样的问题之前,其实可以自己先思考这三个问题:

  • 这道题目我举例推导状态转移公式了么?
  • 我打印dp数组的日志了么?
  • 打印出来了dp数组和我想的一样么?

如果这灵魂三问自己都做到了,基本上这道题目也就解决了,或者更清晰的知道自己究竟是哪一点不明白,是状态转移不明白,还是实现代码不知道该怎么写,还是不理解遍历dp数组的顺序。

然后在问问题,目的性就很强了,群里的小伙伴也可以快速知道提问者的疑惑了。

注意这里不是说不让大家问问题哈, 而是说问问题之前要有自己的思考,问题要问到点子上!

我们工作之后就会发现,特别是大厂,问问题是一个专业活,是的,问问题也要体现出专业!

如果问同事很不专业的问题,同事们会懒的回答,领导也会认为你缺乏思考能力,这对职场发展是很不利的。

所以大家在刷题的时候,就锻炼自己养成专业提问的好习惯。

今天开始新的征程了,加油!!!

509. 斐波那契数

思路

动态规划

动规五部曲:

这里我们要用一个一维dp数组来保存递归的结果

  • 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数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2],我们来推导一下,当N为10的时候,dp数组应该是如下的数列:

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来,发现结果不对,就把dp数组打印出来看看和我们推导的数列是不是一致的。

代码如下:

class Solution {public int fib(int n) {if(n == 0 || n ==1){return n;}//1.确定dp数组下标含义//2.确定递推公式 dp[i] = dp[i-1] + dp[i-2];//3.dp数组初始化int[] dp = new int[n+1];dp[0] = 0;dp[1] = 1;//4.确定遍历顺序:从前往后for(int i = 2;i <= n;i++){dp[i]=dp[i-1]+dp[i-2];}//5.举例推导dp数组return dp[n];}
}

70. 爬楼梯

思路

举几个例子,就可以发现其规律。

爬到第一层楼梯有一种方法,爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ,第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来,那么就可以想到动态规划了。

我们来分析一下,动规五部曲:

定义一个一维数组来记录不同楼层的状态

  • 1/确定dp数组以及下标的含义

dp[i]: 爬到第i层楼梯,有dp[i]种方法

  • 2/确定递推公式

如何可以推出dp[i]呢?

从dp[i]的定义可以看出,dp[i] 可以有两个方向推出来。

首先是dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法,那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法,那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和!

所以dp[i] = dp[i - 1] + dp[i - 2] 。

在推导dp[i]的时候,一定要时刻想着dp[i]的定义,否则容易跑偏。

这体现出确定dp数组以及下标的含义的重要性!

  • 3、dp数组如何初始化

再回顾一下dp[i]的定义:爬到第i层楼梯,有dp[i]种方法。

那么i为0,dp[i]应该是多少呢,这个可以有很多解释,但基本都是直接奔着答案去解释的。

例如强行安慰自己爬到第0层,也有一种方法,什么都不做也就是一种方法即:dp[0] = 1,相当于直接站在楼顶。

但总有点牵强的成分。

那还这么理解呢:卡哥就认为跑到第0层,方法就是0啊,一步只能走一个台阶或者两个台阶,然而楼层是0,直接站楼顶上了,就是不用方法,dp[0]就应该是0.

其实这么争论下去没有意义,大部分解释说dp[0]应该为1的理由其实是因为dp[0]=1的话在递推的过程中i从2开始遍历本题就能过,然后就往结果上靠去解释dp[0] = 1

从dp数组定义的角度上来说,dp[0] = 0 也能说得通。

需要注意的是:题目中说了n是一个正整数,题目根本就没说n有为0的情况。

所以本题其实就不应该讨论dp[0]的初始化!

我相信dp[1] = 1,dp[2] = 2,这个初始化大家应该都没有争议的。

所以卡哥的原则是:不考虑dp[0]如何初始化,只初始化dp[1] = 1,dp[2] = 2,然后从i = 3开始递推,这样才符合dp[i]的定义。

  • 4、确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序一定是从前向后遍历的

  • 5、举例推导dp数组

举例当n为5的时候,dp table(dp数组)应该是这样的

70.爬楼梯

如果代码出问题了,就把dp table 打印出来,看看究竟是不是和自己推导的一样。

此时发现了,这不就是斐波那契数列么!

唯一的区别是,没有讨论dp[0]应该是什么,因为dp[0]在本题没有意义!

代码如下:

class Solution {public int climbStairs(int n) {if(n == 1 || n==2){return n;}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];}
}

746. 使用最小花费爬楼梯

思路

修改之后的题意就比较明确了,题目中说 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于 跳到 下标 0 或者 下标 1 是不花费体力的, 从 下标 0 下标1 开始跳就要花费体力了。

  • 1、确定dp数组以及下标的含义

使用动态规划,就要有一个数组来记录状态,本题只需要一个一维数组dp[i]就可以了。

dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]

对于dp数组的定义,一定要清晰!

  • 2、确定递推公式

可以有两个途径得到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]);

  • 3、dp数组如何初始化

看一下递归公式,dp[i]由dp[i - 1],dp[i - 2]推出,既然初始化所有的dp[i]是不可能的,那么只初始化dp[0]和dp[1]就够了,其他的最终都是dp[0]dp[1]推出。

那么 dp[0] 应该是多少呢? 根据dp数组的定义,到达第0台阶所花费的最小体力为dp[0],那么有同学可能想,那dp[0] 应该是 cost[0],例如 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 的话,dp[0] 就是 cost[0] 应该是1。

这里就要说明本题力扣为什么改题意,而且修改题意之后 就清晰很多的原因了。

新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的,但从 第0 个台阶 往上跳的话,需要花费 cost[0]。

所以初始化 dp[0] = 0,dp[1] = 0;

  • 4、确定遍历顺序

最后一步,递归公式有了,初始化有了,如何遍历呢?

本题的遍历顺序其实比较简单,简单到很多同学都忽略了思考这一步直接就把代码写出来了。

因为是模拟台阶,而且 dp[i]由dp[i-1]dp[i-2] 推出,所以是从前到后遍历cost数组就可以了。

但是稍稍有点难度的动态规划,其遍历顺序并不容易确定下来。 例如:01背包,都知道两个for循环,一个for遍历物品嵌套一个for遍历背包容量,那么为什么不是一个for遍历背包容量嵌套一个for遍历物品呢? 以及在使用一维dp数组的时候遍历背包容量为什么要倒序呢?

这些都与遍历顺序息息相关。当然背包问题后续「代码随想录」都会重点讲解的!

  • 5、举例推导dp数组

拿示例2:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,来模拟一下dp数组的状态变化,如下:

如果代码写出来有问题,就把dp数组打印出来,看看和如上推导的是不是一样的。

代码如下:

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];}
}

第一次接触动态规划,对于一些概念和逻辑不清晰,但经过第一天的引导之后整体对dp有了一个整体的认识。

相关文章:

代码随想录算法训练营第三十八天丨 动态规划part01

动态规划理论基础 动态规划刷题大纲 什么是动态规划 动态规划&#xff0c;英文&#xff1a;Dynamic Programming&#xff0c;简称DP&#xff0c;如果某一问题有很多重叠子问题&#xff0c;使用动态规划是最有效的。 所以动态规划中每一个状态一定是由上一个状态推导出来的&a…...

关于集合遇到的坑

public void invoke(ComparisonSpotEvaluationResultsExcel comparisonSpotEvaluationResultsExcel, AnalysisContext analysisContext) {/*** 记录行号码*/ReadRowHolder readRowHolder analysisContext.readRowHolder();Integer rowIndex readRowHolder.getRowIndex();Stri…...

需要下微信视频号视频的小伙伴们看过来~

随着视频号的热度越来越大&#xff0c;下载视频号视频的需求也开始增加啦&#xff0c;今天给大家给分享几个简单实用的下载方法&#xff0c;总有一个你能用上的&#xff01; 一、犀牛视频下载 犀牛视频下载器可以直接解析并下载视频号短视频。您只需转发视频到机器人即可下载。…...

测试工具:hurl

文章目录 Hurlinstallstartdemo 功能使用变量Capturing values 捕获值Asserts 断言生成报告 Hurl 官网&#xff1a;https://hurl.dev/ Hurl 是一个命令行工具&#xff0c;它运行以简单的纯文本格式定义的 HTTP 请求。 它可以发送请求、捕获值并评估对标头和正文响应的查询 i…...

RateLimiter限流

使用场景 限流是高并发的处理方法之一。 高并发处理方案&#xff1a;  缓存&#xff1a;缓存的目的是提升系统访问速度和增大系统处理容量。 降级&#xff1a;降级是当服务出现问题或者影响到核心流程时&#xff0c;需要暂时屏蔽掉&#xff0c;待高峰或者问题解决后再打开。…...

PMP适合哪些人去考?

许多人都在考虑是否适合考取PMP证书&#xff0c;我来解答你的疑惑&#xff1a;无论是IT、建筑、制药、制造业、电信、金融还是通信领域&#xff0c;PMP证书都得到广泛认可。虽然IT行业目前占比最大&#xff0c;但近几年T业比重下降&#xff0c;制造业、金融、能源和建筑工程等的…...

钡铼技术 工控机中的X86和ARM处理器:哪个更具可扩展性?

X86和ARM是两种不同的处理器架构&#xff0c;它们在工控机中的应用也有所不同。 X86架构的处理器是英特尔公司和AMD公司生产的&#xff0c;它们主要应用于个人电脑和服务器等领域。X86架构的处理器具有良好的通用性和兼容性&#xff0c;可以运行各种操作系统和应用软件。X86架…...

软考 系统架构设计师系列知识点之软件构件(3)

接前一篇文章&#xff1a;软考 系统架构设计师系列知识点之软件构件&#xff08;2&#xff09; 所属章节&#xff1a; 第2章. 计算机系统基础知识 第3节. 计算机软件 2.3.7 软件构件 &#xff08;2&#xff09;J2EE&#xff08;补充知识&#xff09; J2EE核心组成&#xff1a…...

中科驭数亮相2023中国移动全球合作伙伴大会

10月11-13日&#xff0c;2023中国移动全球合作伙伴大会开幕。中科驭数作为移动云COCA生态合作伙伴&#xff0c;受邀出席“算网融百业数智赢未来”政企分论坛&#xff0c;高级副总裁张宇上台参与移动云OpenCOCA开源项目和《OpenCOCA白皮书》的重磅发布仪式&#xff0c;助力构建未…...

WebGIS国产化(信创)研发流程一:数据库的调研与介绍

眼下互联网产业国产化已经成为不可阻挡的趋势&#xff0c;WebGIS的开发工作也不例外&#xff0c;越来越依靠纯国产的软件和产品&#xff0c;甚至是框架。企业中使用国产软件和产品的项目占比也在不断升高&#xff0c;我将分享一系列的文章给大家&#xff0c;来共同研究GIS的国产…...

[Shell] ${} 的多种用法

文章目录 解释代码 解释 在Shell脚本中&#xff0c;${} 是一种变量替换语法。它用于获取和操作变量的值。 具体来说&#xff0c;${} 可以用来执行以下操作&#xff1a; 变量引用&#xff1a;${variable} 表示引用变量 variable 的值。 变量默认值&#xff1a;${variable:-de…...

基于SpringBoot的社区医院管理系统设计与实现

目录 前言 一、技术栈 二、系统功能介绍 管理员功能实现 用户信息管理 病例信息管理 家庭医生管理 药品信息管理 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 信息数据从传统到当代&#xff0c;是一直在变革当中&#xff0c;突如其来的互联网让传统的…...

Spring的执行流程与Bean的生命周期

目录 一、Spring的执行流程&#xff08;生命周期&#xff09; 二、Bean的生命周期 一、Spring的执行流程&#xff08;生命周期&#xff09; 首先在Spring的执行过程中会先启动容器&#xff0c;这里是将配置文件进行加载。根据配置文件完成Bean的实例化&#xff0c;比如是配置的…...

使用 SQL 的方式查询消息队列数据以及踩坑指南

背景 为了让业务团队可以更好的跟踪自己消息的生产和消费状态&#xff0c;需要一个类似于表格视图的消息列表&#xff0c;用户可以直观的看到发送的消息&#xff1b;同时点击详情后也能查到消息的整个轨迹。 消息列表 点击详情后查看轨迹 原理介绍 由于 Pulsar 并没有关系型数…...

拿下国家级信创认证 中科驭数KPU SWIFT-2200N成为国内首款满足金融业严苛要求的DPU产品

近日&#xff0c;中科驭数KPU SWIFT-2200N低时延DPU卡&#xff0c;在中国人民银行旗下金融信创生态实验室完成测试并取得测试报告&#xff0c;这意味着中科驭数低时延网络代表性产品的应用领域从证券进一步拓展到了银行业&#xff0c;成为国内首款满足金融行业严苛要求的DPU产品…...

centos怎么禁用和关闭selinux

要禁用和关闭SELinux(Security-Enhanced Linux)在CentOS上&#xff0c;请按照以下步骤进行&#xff1a; 请注意&#xff1a;禁用SELinux会减少系统的安全性&#xff0c;因此只有在确切知道自己在做什么并且出于特定目的时才应该这样做。 1.打开终端并以超级用户(root)身份登录&…...

【LeetCode刷题日志】88.合并两个有序数组

&#x1f388;个人主页&#xff1a;库库的里昂 &#x1f390;C/C领域新星创作者 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏✨收录专栏&#xff1a;LeetCode 刷题日志&#x1f91d;希望作者的文章能对你有所帮助&#xff0c;有不足的地方请在评论区留言指正&#xff0c;…...

计算机考研 | 2013年 | 计算机组成原理真题

文章目录 【计算机组成原理2013年真题43题-9分】【第一步&#xff1a;信息提取】【第二步&#xff1a;具体解答】 【计算机组成原理2013年真题44题-14分】【第一步&#xff1a;信息提取】【第二步&#xff1a;具体解答】 【计算机组成原理2013年真题43题-9分】 某32位计算机&a…...

[Unity][VR]透视开发系列4-解决只看得到Passthrough但看不到Unity对象的问题

【视频资源】 视频讲解地址请关注我的B站。 专栏后期会有一些不公开的高阶实战内容或是更细节的指导内容。 B站地址: https://www.bilibili.com/video/BV1Zg4y1w7fZ/ 我还有一些免费和收费课程在网易云课堂(大徐VR课堂): https://study.163.com/provider/480000002282025/…...

电气工程 自动化 机械工科学生来看看

PLC 类 基于PLC的机械手控制系统设计 基于PLC的机械手控制系统设计 PLC与变频器在综采设备上的应用 PLC与步进电机的运动控制编程9000 PLC应用数字电子钟设计 三菱FX系列PLC与三菱变频器通讯应用实例 基于plc拉杆箱振动与噪音检测平台设计 基于PLC的船舶空压机控制系统设计 基…...

NewStarCTF2023week4-midsql(利用二分查找实现时间盲注攻击)

大致测试一下&#xff0c;发现空格被过滤了 使用内联注释/**/绕过&#xff0c;可行 1/**/-- 使用%a0替代空格&#xff0c;也可以 1%a0-- 再次测试发现等号也被过滤&#xff0c;我们使用 like 代替 &#xff08;我最开始以为是and被过滤&#xff0c;并没有&#xff0c;如果是…...

null,undefined的区别?

在 JavaScript 中,null 和 undefined 都表示没有值或缺失值的状态,但它们之间有一些区别。 null: null 是一个表示空值的特殊关键字。它是一个表示变量未赋值的值,可以将其赋给任何变量,表示该变量为空。使用 null 可以明确地将一个变量设置为空。 示例: let myVaria…...

2.flink编码第一步(maven工程创建)

概述 万里第一步&#xff0c;要进行flink代码开发&#xff0c;第一步先整个 flink 代码工程 flink相关文章链接 flink官方文档 两种方式 一种命令行 mvn 创建&#xff0c;另一种直接在 idea 中创建一个工程&#xff0c;使用 mvn 的一些配置 mvn命令行创建 mvn 创建flink工程&…...

Unit1_1:分治问题之时间复杂度求解

文章目录 背景递归树法案例一案例二局限性 代入法/替代法主方法&#xff08;重点&#xff09; 背景 当碰到形如 T ( n ) a T ( ⌈ n b ⌉ ) O ( n d ) T(n)aT(\lceil \frac{n}{b} \rceil)O(n^d) T(n)aT(⌈bn​⌉)O(nd)的递推式&#xff0c;本质上就是将问题转化为规模更小的…...

React hooks的闭包陷阱

react hooks 陷阱 hooks必须放在函数顶层&#xff0c; 不能在条件分支和方法内 1、useState陷阱 异步陷阱 function Index() {const [count, setCount] useState(0)function add(){setCount( count 1 )console.log(count); // 0}return (<div><span>{count}…...

20.3 OpenSSL 对称AES加解密算法

AES算法是一种对称加密算法&#xff0c;全称为高级加密标准&#xff08;Advanced Encryption Standard&#xff09;。它是一种分组密码&#xff0c;以128比特为一个分组进行加密&#xff0c;其密钥长度可以是128比特、192比特或256比特&#xff0c;因此可以提供不同等级的安全性…...

一文详解防御DDoS攻击的几大有效办法

伴随互联网的飞速发展&#xff0c;网络安全问题变得越来越突出&#xff0c;其中最常见的就是DDoS攻击&#xff0c;也就是分布式拒绝服务攻击。DDoS攻击者利用计算机或其他设备的协作&#xff0c;以发送大量请求的方式导致目标超负荷&#xff0c;导致不能正常运转或“宕机”。以…...

Python二级 每周练习题24

练习一: 体重比较器 要求: 请编程实现如下功能: (1)程序开始运行时&#xff0c;提醒用户输入三个人的名字和体重 (可以分开输入&#xff0c;每次输入名字或者体重) (2) 程序自动比较&#xff0c;找出最重的一个人的名字和体重输出 的格式不限&#xff0c;但是要有最重人的姓名…...

MySQL - Buffer Pool

Buffer Pool 主要用于缓存数据库表的数据页&#xff0c;以提高数据库的读取性能&#xff1a; 缓存数据页&#xff1a;Buffer Pool 是 MySQL 中用于缓存数据页的内存区域。数据页通常包含数据库表的数据&#xff0c;如行记录等。当查询或读取数据时&#xff0c;MySQL会首先查看…...

c++ 拆分函数返回值和参数类型

在c中&#xff0c;函数参数类型和返回值类型通常是一个比较明确的信息&#xff0c;好像确实无需在这个上面费周折。然而&#xff0c;硬编码数据类型会让代码复用性下降&#xff0c;如果能够通过某种方式自动获取函数参数和返回值类型&#xff0c;对于代码的可复用性&#xff0c…...