java数据结构与算法刷题-----LeetCode198. 打家劫舍

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

很多人觉得动态规划很难,但它就是固定套路而已。其实动态规划只不过是将多余的步骤,提前放到dp数组中(就是一个数组,只不过大家都叫它dp),达到空间换时间的效果。它仅仅只是一种优化思路,因此它目前的境地和线性代数一样----虚假的难。

  1. 想想线性代数,在国外留学的学生大多数不觉得线性代数难理解。但是中国的学生学习线性代数时,完全摸不着头脑,一上来就是行列式和矩阵,根本不知道这玩意是干嘛的。
  2. 线性代数从根本上是在空间上研究向量,抽象上研究线性关系的学科。人家国外的教科书都是第一讲就帮助大家理解研究向量和线性关系。
  3. 反观国内的教材,直接把行列式搞到第一章。搞的国内的学生在学习线性代数的时候,只会觉得一知半解,觉得麻烦,完全不知道这玩意学来干什么。当苦尽甘来终于理解线性代数时干什么的时候,发现人家国外的教材第一节就把这玩意讲清楚了。你只会大骂我们国内这些教材,什么狗东西(以上是自己学完线性代数后的吐槽,我们同学无一例外都这么觉得)。

而我想告诉你,动态规划和线性代数一样,我学完了才知道,它不过就是研究空间换时间,提前将固定的重复操作规划到dp数组中,而不用暴力求解,从而让效率极大提升。

  1. 但是网上教动态规划的兄弟们,你直接给一个动态方程是怎么回事?和线性代数,一上来就教行列式和矩阵一样,纯属恶心人。我差不多做了30多道动态规划题目,才理解,动态方程只是一个步骤而已,而这已经浪费我很长时间了,我每道题都一知半解不理解,过程及其痛苦。最后只能重新做。
  2. 动态规划,一定是优先考虑重复操作与dp数组之间的关系,搞清楚后,再提出动态方程。而你们前面步骤省略了不讲,一上来给个方程,不是纯属扯淡吗?
  3. 我推荐研究动态规划题目,按5个步骤,从上到下依次来分析
  1. DP数组及下标含义
  2. 递推公式
  3. dp数组初始化
  4. 数组遍历顺序(双重循环及以上时,才考虑)
  5. dp数组打印,分析思路是否正确(相当于做完题,检查一下)

在这里插入图片描述

在这里插入图片描述

先理解题目细节

想象这样一个场景,我们是小偷,从第一栋挨个考虑偷还是不偷,如果偷,那就是身上已经偷了多少+这一栋能偷多少。如果不偷,那就是身上已经偷了多少。

在这里插入图片描述

  1. 题目给我们的数组代表每个房子有多少钱,而且相邻的房子不能都偷,只能偷不相邻的。
  2. 例如2,1,1,2 这个序列,显然不触发警报的前提下(不偷相邻的)----偷第一个和第4个为能偷到的最多的钱
  3. 怎么偷才能偷到最多呢?当然是保证最大获利情况下,能偷的都偷了,而且不能触发警报。
  4. 我们每个房子都单独考虑,偷还是不偷,而且只需考虑它前面的房子,因为我们要能偷的都偷
  1. 若要偷当前房子:那么,前面相邻的不能考虑,只能考虑再前面一个,也就是当前房子的金额,加上除了前面一个相邻的房子外,已经偷了多少。
  2. 若不偷当前房子:那么,前面偷了多少,到这个房子就还有多少,金额不变
解题思路
  1. 暴力求解的思想,就是回溯算法,枚举每一种情况,拿到最大值,显然会做大量无效运算。
  2. 但是如果我们预先将其存储到dp数组,就可以直接通过dp[x], 获取dp数组中指定位置x的体力花费,而不用枚举。典型的动态规划题目
动态规划思考5步曲
  1. DP数组及下标含义

我们要求出的是到了某个房子后最大情况下偷了多少钱,那么dp数组中存储的就是最大情况下偷了多少钱。要求出谁的最大情况下偷了多少。显然是到达某个房子后,那么下标就是代表现在到了哪个房子,也就是代表到了某一栋房子后的最大已偷取的金额。显然,只需要一个下标即可表示,故这道题的dp数组只需要一维数组

  1. 递推公式
  1. 由题意可知,每个房子都可以选择偷与不偷,选择最大值。而第一个房子肯定要偷它,才能获得最大值。而第二个房子,因为它前面没有不相邻的房子,所以它要么不偷,也就是只偷第一个房子。要么选择偷第二个房子,而第一个房子不偷,然后选择最大情况。

故:第一个房子固定为F(0) = 第一个房子金额。第二个固定为F(1) = max(第一个房子金额,第二个房子金额)

  1. 之后每一栋,都需要判断它偷还是不偷,以及前面不相邻的房子。如果偷,就要考虑前面不相邻的+自己这栋能偷多少钱。不偷,那么前一栋相邻的它肯定考虑一下。而前面的房子怎么考虑的是前面房子的事,它们也考虑过了偷还是不偷。我们只考虑当前这栋是偷,还是不偷
  2. 因此,可以得到,从第三栋开始,递推公式为偷或者不偷,选择最大值: F(n) = max( F(n-2)+nums[n] , F(n-1) )
  1. dp数组初始化

在这里插入图片描述

  1. 数组遍历顺序(因为这个数列是一维的,只需要一重循环,无需考虑这个)
  2. 打印dp数组(自己生成dp数组后,将dp数组输出看看,是否和自己预想的一样。)

在这里插入图片描述

代码:时间复杂度O(n).空间复杂度O(n)

在这里插入图片描述

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;//有多少栋房子
        int dp[] = new int[length];//dp数组
        dp[0] = nums[0];//第一栋,只能选择偷它
        //第二栋可以选择偷(那么第一栋不能偷),或者不偷(只偷第二栋,第一栋不偷),无需考虑前面不相邻的
        if(length>=2) dp[1] = Math.max(nums[0],nums[1]);
        //第三栋开始,不仅仅要考虑偷还是不偷,还要考虑前面不相邻的
        for(int i = 2;i<length;i++){
            //如果这一栋不偷,则前面偷了多少就是多少,也就是到上一栋时,有多少就有多少===dp[i-1]
            //如果这一栋要偷,则前面不相邻的偷了多少 + 这一栋有多少 为偷完这一栋拿到的钱
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);//我们只考虑最大情况
        }
        return dp[length-1];//返回偷到最后一栋时,偷到的最大金额
    }
}
学有余力的同学可以尝试这个方法,将空间复杂度变为常数级-----------------代码:时间复杂度O(n).空间复杂度O(1)

将dp数组优化掉,换成3个变量,滚动执行。将dp[0]换成first。dp[1]换成second. 也就是first永远指向当前栋的前面不相邻的,second永远指向前面相邻的。
在这里插入图片描述

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;//有多少栋房子
        int first = nums[0],second = nums[0];//第一栋,只能选择偷它
        //第二栋可以选择偷(那么第一栋不能偷),或者不偷(只偷第二栋,第一栋不偷),无需考虑前面不相邻的
        if(length>=2) second = Math.max(nums[0],nums[1]);
        //第三栋开始,不仅仅要考虑偷还是不偷,还要考虑前面不相邻的
        for(int i = 2;i<length;i++){
            int temp = second;
            second = Math.max(first+nums[i],second);//我们只考虑最大情况
            first = temp;
        }
        return second;//返回偷到最后一栋时,偷到的最大金额
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

第6节、T型加减速转动【51单片机+L298N步进电机系列教程】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;本章介绍步进电机T型加减速的控制方法&#xff0c;分三个小节&#xff0c;本小节主要内容为该控制方法的推导与计算。目前各平台对该控制方法介绍的文章目前较多&#xff0c;但部分关键参数并未给出推导…

莉莉与神奇花朵的冒险

现在&#xff0c;我将根据这些步骤编写一个对话形式的童话故事。 在很久很久以前的一个小村庄里&#xff0c;有一个勤劳善良的小女孩叫莉莉。她住在一间小茅屋里&#xff0c;和她的奶奶一起生活。奶奶年纪大了&#xff0c;行动不便&#xff0c;所以莉莉每天都要照顾她。 一天&a…

游戏开发-会飞的小鸟(已完结,附源码)

游戏开发-会飞的小鸟&#xff08;已完结&#xff0c;附源码&#xff09; 你将学到的课程链接详细介绍 你将学到的 掌握Java编程的基本技能开发出自己的“会飞的小鸟”游戏对面向对象编程有深刻的理解学会运用常见算法和数据结构解决问题能够独立调试和优化自己的代码 课程链接…

NLP_循环神经网络(RNN)

文章目录 RNN结构RNN实战RNN小结 RNN结构 NPLM 在处理长序列时会面临一些挑战。首先&#xff0c;由于它仍然是基于词的模型&#xff0c;因此在处理稀有词汇或者词汇表外的词汇时效果不佳。其次&#xff0c;NPLM不能很好地处理长距离依赖关系。而上面这两个局限&#xff0c;恰恰…

【芯片设计- RTL 数字逻辑设计入门 8 -- 四选一多路器】

文章目录 四选一多路输出器verilog case 语句verilog 代码testbench 代码仿真波形 问题小结 四选一多路输出器 制作一个四选一的多路选择器&#xff0c;要求输出定义上为线网类型 状态转换&#xff1a; d0 00 d1 01 d2 10 d3 11verilog case 语句 case(express…

蓝桥杯Web应用开发-CSS 基础语法4(字体属性、链接中的伪类、列表样式)

专栏持续更新中 字体属性 字体属性用于定义字体的类型、字号大小、加粗、斜体等方面样式。常用的字体属性如下表所示&#xff1a; 属 性可 取 值描 述fontfont-style、font-variant、font-weight、font-size&#xff08;或 line-height&#xff09;、font-family在一个声明中…

如何使用Docker部署DashDot服务器仪表盘并结合cpolar实现公网访问

&#x1f4d1;前言 本文主要是使用Docker部署DashDot服务器仪表盘并结合cpolar实现公网访问的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️** &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是青衿&#x1f947; ☁️博客首页&#xff1a;CSDN主页放风…

go语言每日一练——链表篇(六)

传送门 牛客面试必刷101题—— 判断链表中是否有环 牛客面试必刷101题—— 链表中环的入口结点 题目及解析 题目一 代码 package mainimport . "nc_tools"/** type ListNode struct{* Val int* Next *ListNode* }*//**** param head ListNode类* return bool…

算法笔记刷题日记——3.简单入门模拟 3.2 查找元素

刷题日记 3.2 查找元素 B1041 B1004 B1028 B1032 A1011 A1006 A1036 错题记录 B1028 人口普查 某城镇进行人口普查&#xff0c;得到了全体居民的生日。现请你写个程序&#xff0c;找出镇上最年长和最年轻的人。 这里确保每个输入的日期都是合法的&#xff0c;但不一定是合理的…

网工内推 | 上市公司运维岗,红帽认证优先,带薪年假,节日福利

01 捷科智诚 招聘岗位&#xff1a;配置管理岗-运维 职责描述&#xff1a; 1.负责日常配置管理平台的维护及优化&#xff0c;包括权限管理、基线管理、版本管理、发布管理、变更管理等&#xff1b; 2.负责维护各个管理平台的用户管理、权限管理、项目初始化等工作&#xff1b; …

一些常见的电源方案

开关电源&#xff1a; RM C 板&#xff1a;&#xff08;24V电压&#xff0c;10A电流&#xff09; SMBJ30CA&#xff1a;静电和浪涌保护(TVS/ESD) 一般使用NMOS管&#xff0c;因为PMOS管导通电阻与NMOS管比较会较大 模电非基础01——从一种常见的防反接&#xff0c;上电缓启…

【深度学习理论】持续更新

文章目录 1.统计学习理论 1.统计学习理论 统计学习理论&#xff0c;一款适合零成本搞深度学习的大冤种的方向 从人类学习到机器学习的对比&#xff08;学习的过程分为归纳和演绎 &#xff09;&#xff0c;引出泛化和过拟合的概念。 如何表示归纳的函数规律呢&#xff1f;以监督…

RP2040 SPI

SPI 的库文件是arduino开源库&#xff0c;在程序中include。 SPI IIC都是通信协议【模块】&#xff0c;需要硬件支持&#xff0c;MCU都会集成相应的模块。arduino都集成在了内核中&#xff0c;直接用API函数调用即可。其他单片机的架构也是相同的。 SPI的库和函数及其相关说明…

NLP_词的向量表示Word2Vec 和 Embedding

文章目录 词向量Word2Vec&#xff1a;CBOW模型和Skip-Gram模型通过nn.Embedding来实现词嵌入Word2Vec小结 词向量 下面这张图就形象地呈现了词向量的内涵:把词转化为向量&#xff0c;从而捕捉词与词之间的语义和句法关系&#xff0c;使得具有相似含义或相关性的词语在向量空间…

2024牛客寒假算法基础集训营1——H

输入 3 4 11 1 8 1 4 1 5 1 1 4 11 5 8 1 4 1 5 1 1 4 0 2 0 0 0 3 0 4 1 输出 3 6 5 思路&#xff1a; 考虑二进制&#xff0c;有点像数位dp 本题考虑集合划分&#xff0c;累加最大值即可 代码如下&#xff1a; #include<bits/stdc.h> using namespace std;void solv…

2024三掌柜赠书活动第八期:Web3与DAO:下一代互联网演进逻辑

目录 前言关于Web3和DAO关于《Web3与DAO&#xff1a;下一代互联网演进逻辑》编辑推荐内容简介作者简介精彩书评图书目录书中前言/序言《Web3与DAO&#xff1a;下一代互联网演进逻辑》全书速览结束语 前言 随着区块链技术的崛起&#xff0c;Web3和DAO成为了当前互联网领域炙手…

【达梦数据库】使用DBeaver管理达梦数据库

使用DBeaver管理达梦数据库 Step1 安装相关程序 达梦8数据库DBeaver社区版 Step2 新建驱动 类型参数驱动名称DM8驱动类型Generic类名dm.jdbc.driver.DmDriverURL模板jdbc:dm://{host}:{port}默认端口5236默认数据库默认用户SYSDBA Step3 连接服务

docker部署笔记系统flatnotes

效果 安装 创建目录 mkdir -p /opt/flatnotes/data && cd /opt/flatnotes/ chmod -R 777 /opt/flatnotes/ 创建并启动容器(可以自己修改账户和密码) docker run -d \ --restart unless-stopped \ --name flatnotes \ -p "10040:8080" \ -v "/dat…

vue3 之 组合式API—生命周期函数

vue3的生命周期API 生命周期函数基本使用 1️⃣导入生命周期函数 2️⃣执行生命周期函数 传入回调 <scirpt setup> import { onMounted } from vue onMounted(()>{// 组件挂载完毕mounted执行了 }) </script>执行多次 生命周期函数是可以执行多次的&#xff…

【pikachu csrf】

cxrf 个人理解getPOST 个人理解 当被攻击用户登陆访问网站时&#xff0c;在保持登陆状态时点击小黑子&#xff08;黑客&#xff09;搭建的恶意链接而导致用户受到攻击。 举个例子 我去攻击网站&#xff0c;但是我找不到漏洞&#xff0c;这个时候我注册一个账号&#xff0c;发现…