代码随想录-刷题第三十九天

动态规划理论基础

动态规划的题目由重叠子问题构成,每一个状态一定是由上一个状态推导出来的。这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的。

动态规划五步曲

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

动态规划里面递推公式十分重要,但是确定dp数组,初始化,遍历顺序也同样十分重要,一定要严格按照这五步进行,将每一步的思路理清。

做动态规划的题目遇到问题时,最好的方式就是打印出dp数组,看是否和自己推理一致。


509. 斐波那契数

题目链接:509. 斐波那契数

思路:动态规划五步曲:

  1. dp[i]的定义为:第i个数的斐波那契数值是dp[i]

  2. 递推公式:dp[i] = dp[i - 1] + dp[i - 2]

  3. 初始化:dp[0] = 0, dp[1] = 1

  4. 从递推公式可以看出,一定是从前向后遍历的。

  5. 举例看是否可行,当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) return 0;if (n == 1) return 1;             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];}
}

可以发现,只需要维护两个数值,不需要记录整个序列。代码如下:

class Solution {public int fib(int n) { // 动态规划if (n <= 1) return n;int dp0 = 0;int dp1 = 1;for (int i = 2; i <= n; i++) {int sum = dp1 + dp0;dp0 = dp1;dp1 = sum;}return dp1;}
}

70. 爬楼梯

题目链接:70. 爬楼梯

思路:动态规划五步曲

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

  2. 递推公式:dp[i] = dp[i - 1] + dp[i - 2]

    从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]的定义,否则容易跑偏。

  3. 初始化:dp[1] = 1, dp[2] = 2

    题目提示:1 <= n <= 45,所以本题不用考虑dp[0]的初始化!

  4. 从递推公式可以看出是从前向后遍历。

  5. 举例看是否可行

class Solution {public int climbStairs(int n) {if (n == 1) return 1;// 1、确定dp数组及下标含义// dp[i]代表爬到第i层楼梯,有dp[i]种方法int[] dp = new int[n + 1];// 2、确定递推函数// dp[i] = dp[i - 1] + dp[i - 2]// 3、确定初始化dp[1] = 1;dp[2] = 2;// 4、确定遍历顺序for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

本题与斐波那契数相同,可以将空间复杂度从O(n)降为O(1)。


746. 使用最小花费爬楼梯

题目链接:746. 使用最小花费爬楼梯

思路:动态规划五步曲

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

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

  2. 递推公式:dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 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]跳呢?一定是选最小的!

  3. 初始化:dp[0] = 0, dp[1] = 0。我们认为第一步无需支付费用,所以到第一个台阶和到第二个台阶都是0。

  4. 遍历顺序为从前到后

  5. 举例推导dp数组

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

    img

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

class Solution {public int minCostClimbingStairs(int[] cost) {int len = cost.length;int[] dp = new int[len + 1];// 每次最多走两步,前两个台阶无需支付费用dp[0] = 0;dp[1] = 0;// 计算到达每一层台阶的最小费用for (int i = 2; i <= len; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[len];}
}

还可以优化空间复杂度,因为dp[i]就是由前两位推出来的,那么也不用dp数组了

class Solution {public int minCostClimbingStairs(int[] cost) {int len = cost.length;// 每次最多走两步,前两个台阶无需支付费用int dp0 = 0;int dp1 = 0;// 计算到达每一层台阶的最小费用for (int i = 2; i <= len; i++) {int dp_i = Math.min(dp1 + cost[i - 1], dp0 + cost[i - 2]);dp0 = dp1;dp1 = dp_i;}return dp1;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

MySQL按月分片

一、按照月分片 使用场景为按照自然月来分片,每个自然月为一个分片,但是一年有12个月,是不是要有12个数据节点才行呢?并不是。例如我现在只有三个分片数据库,这样就可以1月在第一个数据分片中,2月在第二个数据分片中,3月在第三个数据分片中,当来到4月的时候,就会重新开…

w4操作系统之windows上创建隐藏用户

隐藏用户–在windows上创建隐藏用户 1.首先查看现有哪些用户。&#xff08;通过net user 命令&#xff09; 2.然后创建隐藏用户&#xff08;net user client$ 123 /add&#xff09; 此时出现报错信息。原因是登录用户没权限。需要用管理员的权限 3.用管理员身份运行cmd&am…

【数据结构】C语言实现单链表的基本操作

单链表基本操作的实现 导言一、查找操作1.1 按位查找1.1.1 按位查找的C语言实现1.1.2 按位查找的时间复杂度 1.2 按值查找1.2.1 按值查找的C语言实现1.2.2 按值查找的时间复杂度 二、插入操作2.1 后插操作2.2 前插操作 三、删除操作结语 导言 大家好&#xff0c;很高兴又和大家…

代码随想录二刷 | 二叉树 | 最大二叉树

代码随想录二刷 &#xff5c; 二叉树 &#xff5c; 最大二叉树 题目描述解题思路代码实现 题目描述 654.最大二叉树 给定一个不重复的整数数组 nums 。 最大二叉树可以用下面的算法从 nums 递归地构建: 创建一个根节点&#xff0c;其值为 nums 中的最大值。递归地在最大值 左…

SpringSecurity6 | 默认用户生成(上)

✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: Java从入门到精通 ✨特色专栏: MySQL学习 🥭本文内容:SpringSecurity6 | 默认用户生成(上) 📚个人知识库: [Leo知识库]https://gaozim…

基于STM8S103F3P6的超声波测距仪设计

大三的时候给大四学长做的毕业设计题目 文章目录 1 绪论1.1 设计背景1.2 设计的主要任务 2 超声波测距基本理论及总体架构2.1 基本知识2.1.1 超声波特性2.1.2 超声波传感器2.1.3 超声波测距原理 2.2 总体架构2.2.1 设计原则2.2.2 总体方案介绍 2.3 主要器件选择与介绍2.3.1 主控…

网盘项目话术(0.5w字精选)

功能结构图 数据库设计总结 该项目主要就是对文件的操作&#xff0c;file表&#xff0c;file_share表。 file表主要字段&#xff1a;id&#xff0c;用户id&#xff0c;父级目录id&#xff0c;文件的地址&#xff0c;文件的封面图片地址&#xff0c;创建和修改时间。 file_sha…

react 之 美团案例

1.案例展示 2.环境搭建 克隆项目到本地&#xff08;内置了基础静态组件和模版&#xff09; git clone http://git.itcast.cn/heimaqianduan/redux-meituan.git 安装所有依赖 npm i 启动mock服务&#xff08;内置了json-server&#xff09; npm run serve 启动前端服务 npm…

Translation翻译插件

Translation插件是为IntelliJ IDEA开发的&#xff0c;因此只能在IntelliJ IDEA中使用。但是&#xff0c;如果你需要在其他软件中进行翻译&#xff0c;可以考虑使用其他的翻译工具或服务。例如&#xff0c;一些在线翻译网站&#xff08;如Google翻译、百度翻译等&#xff09;提供…

VScode——下载、安装、配置C/C++环境(windows)

一.快速下载 还在因为vscode官方下载慢而头疼嘛&#xff0c;按这个步骤来直接起飞兄弟萌 首先进入vscode官方网站然后选择对应版本下载然后进入浏览器下载页面复制下载链接粘贴到地址栏 将地址中的/stable前换成vscode.cdn.azure.cn 即可实现超速下载 下面是一个国内镜像的下…

mysql原理--MySQL基于规则的优化

设计 MySQL 的大叔依据一些规则&#xff0c;竭尽全力的把一些很糟糕的语句转换成某种可以比较高效执行的形式&#xff0c;这个过程也可以被称作 查询重写 &#xff08;就是人家觉得你写的语句不好&#xff0c;自己再重写一遍&#xff09;。 1.条件化简 我们编写的查询语句的搜…

vue虚拟列表展示

效果图 <template><!-- 总体高度区域 --><divref"listWrap"class"m-container"scroll"scrollListener"><div:style"handleContainerHeight()"><!-- 可视区域 --><divclass"m-area":style&…

打地鼠游戏来了

主要利用js鼠标点击事件和window.setInterval&#xff08;&#xff09;回调函数来进行实现的. 源码获取方式&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1eW9qvX3zFH9qlH82-I4yOA 提取码&#xff1a;1233

中间件系列 - Redis入门到实战(原理篇)

前言 学习视频&#xff1a; 黑马程序员Redis入门到实战教程&#xff0c;深度透析redis底层原理redis分布式锁企业解决方案黑马点评实战项目 中间件系列 - Redis入门到实战 本内容仅用于个人学习笔记&#xff0c;如有侵扰&#xff0c;联系删除 学习目标 Redis数据结构Redis网…

Matlab:非线性规划

1、语法&#xff1a; xfmincon(fun,x0,A,b) xfmincon(fun,x0,A,b,Aeq,beq) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) xfmincon(problem) [x,fval]fmincon(___) [x,fval,exitflag,…

搭建FTP服务器详细介绍

一.FTP简介 &#xff11;.&#xff11;什么是FTP &#xff11;.&#xff12;FTP服务器介绍 &#xff11;.&#xff13;FTP服务器优缺点 二.FTP服务器的搭建与配置 2.1 开启防火墙 2.2创建组 2.3创建用户 2.4安装FTP服务器 2.5配置FTP服务器 &#xff12;.&#xff…

日常中msvcp120.dll丢失五种解决方法

在日常使用电脑的过程中&#xff0c;我们可能会遇到一些错误提示&#xff0c;其中之一就是“msvcp120.dll丢失”。那么&#xff0c;msvcp120.dll到底是什么&#xff1f;它的作用又是什么呢&#xff1f;为什么会出现丢失的情况呢&#xff1f;本文将为您详细介绍msvcp120.dll的相…

无法连接虚拟机设备 ide1:0,因为主机上没有相应的设备。您要每次在开启此虚拟机时都尝试连接此虚拟设备吗?

Vmware报错&#xff1a; 报错原因&#xff1a; ide1:0一般是虚拟机的光驱&#xff0c;配置选项是“使用物理驱动器”&#xff0c;而宿主机可能没有安装光驱&#xff0c;故无法从驱动器上寻找 .ISO 系统文件。 解决方法: 右键点击对应的虚拟机&#xff0c;再点击“设置”按钮。…

百度每天20%新增代码由AI生成,Comate SaaS服务8000家客户 采纳率超40%

12月28日&#xff0c;由深度学习技术及应用国家工程研究中心主办的WAVE SUMMIT深度学习开发者大会2023在北京召开。百度首席技术官、深度学习技术及应用国家工程研究中心主任王海峰现场公布了飞桨文心五载十届最新生态成果&#xff0c;文心一言最新用户规模破1亿&#xff0c;截…

轻量应用服务器与云服务器CVM对比——腾讯云

腾讯云轻量服务器和云服务器CVM该怎么选&#xff1f;不差钱选云服务器CVM&#xff0c;追求性价比选择轻量应用服务器&#xff0c;轻量真优惠呀&#xff0c;活动 https://curl.qcloud.com/oRMoSucP 轻量应用服务器2核2G3M价格62元一年、2核2G4M价格118元一年&#xff0c;540元三…