DP(7) | 打家劫舍① | Java | LeetCode 198, 213, 337 做题总结(未完)
打家劫舍问题
来源于代码随想录:https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html#%E6%80%9D%E8%B7%AF
① 确定dp数组(dp table)以及下标的含义
dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。
② 确定递推公式
决定dp[i]的因素就是第i房间偷还是不偷。
-
偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ,即:第i-1房一定是不考虑的,找出 下标i-2(包括i-2)以内的房屋,最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
-
不偷第i房间,那么dp[i] = dp[i - 1],即考 虑i-1房,(注意这里是考虑,并不是一定要偷i-1房,这是很多同学容易混淆的点)
然后dp[i]取最大值, 即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
③ dp数组初始化
从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出,递推公式的基础就是dp[0] 和 dp[1]
从dp[i]的定义上来讲,dp[0] 一定是 nums[0],dp[1]就是nums[0]和nums[1]的最大值即:dp[1] = max(nums[0], nums[1]);
④ 确定遍历顺序
dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历
⑤ 举例推导dp数组(略)
198.打家劫舍
class Solution {public int rob(int[] nums) {if(nums.length == 1) return nums[0];int[] dp = new int[nums.length+1];dp[0] = nums[0];dp[1] = nums[0]>nums[1]?nums[0]:nums[1];for(int i=2; i<nums.length; i++) {dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);}return dp[nums.length-1];}
}
213.打家劫舍II
和打家劫舍1区别在,成环-首尾相连
因为首元素和尾元素不能同时存在,所以有三种情况。
三个情况
①不考虑首元素也不考虑尾元素
②考虑首不考虑尾:相当于没有尾元素
③考虑尾不考虑首:
注意情况②③是包含情况①的
class Solution {public int rob(int[] nums) {if(nums.length == 1) return nums[0];if(nums.length == 2) return Math.max(nums[0], nums[1]);return Math.max(robAction(nums,0,nums.length-2), robAction(nums,1,nums.length-1));}public int robAction(int[] nums, int start, int end) {int len = end-start+1;int[]dp = new int[len]; //end-start+1长度dp[0] = nums[start];dp[1] = Math.max(dp[0], nums[start+1]);for(int i=2; i<len; i++) {dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i+start]);}return dp[len-1];}
}
出错点
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i+start]); dp数组的下标是从0开始,但是nums数组的取值要加上start
337.打家劫舍III
相关文章:
DP(7) | 打家劫舍① | Java | LeetCode 198, 213, 337 做题总结(未完)
打家劫舍问题 来源于代码随想录:https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html#%E6%80%9D%E8%B7%AF ① 确定dp数组(dp table)以及下标的含义 dp[i]:考虑下标i(包括i)以内的房…...
人工智能算法工程师(中级)课程17-模型的量化与部署之剪枝技巧与代码详解
大家好,我是微学AI,今天给大家介绍一下人工智能算法工程师(中级)课程17-模型的量化与部署之剪枝技巧与代码详解。模型剪枝是深度学习领域中一项关键的技术,旨在减少神经网络中的冗余权重,从而降低计算成本和内存占用,同…...
JavaScript 实例:掌握编程技巧
JavaScript 实例:掌握编程技巧 JavaScript 是一种广泛使用的编程语言,它为网页添加交互性,是现代网络开发的重要组成部分。本文将通过一系列实例,帮助您更好地理解和掌握 JavaScript 的核心概念和编程技巧。 基础实例:变量和数据类型 首先,让我们从最基础的开始。Java…...
自己做小项目时,配置的Maven需要用阿里云私服加速Jar包的下载
在我的IDEA中,maven配置在了这个地址,然后我需要去这个地址下找到settings.xml的maven配置文件来配置以下的阿里云私服地址来加速jar包的下载!【不然就是下N年很慢!】...
Linux笔记之time命令测量命令的执行时间
Linux笔记之time命令测量命令的执行时间 在Linux中,time命令用于测量命令的执行时间。这对于分析和优化脚本或程序的性能非常有用。time命令会显示三个主要时间指标: real: 从命令开始到结束的实际时间(也称为挂钟时间)。user: …...
《基于 CDC、Spark Streaming、Kafka 实现患者指标采集》
📢 大家好,我是 【战神刘玉栋】,有10多年的研发经验,致力于前后端技术栈的知识沉淀和传播。 💗 🌻 CSDN入驻不久,希望大家多多支持,后续会继续提升文章质量,绝不滥竽充数…...
重要的单元测试
👽System.out.println(“👋🏼嗨,大家好,我是代码不会敲的小符,目前工作于上海某电商服务公司…”); 📚System.out.println(“🎈如果文章中有错误的地方,恳请大家指正&…...
什么是diff算法?
Diff算法,全称为Difference算法,是一种用于比较和查找两个对象(如文本、源代码、数据结构或任何形式的字符串)之间差异的算法。它在多个领域有着广泛的应用,包括但不限于前端开发、版本控制系统、协同编辑工具等。以下…...
BUUCTF逆向wp [MRCTF2020]Transform
第一步 查壳。该题为64位。 第二步 进入主函数,跟进dword_40F040,它应该与关键字符串有关 分析一下: 初始化和输入 sub_402230(argc, argv, envp); 这行可能是一个初始化函数,用于设置程序环境或处理命令行参数。具体功能不明,…...
前端下载文件流 出现乱码 解决方案
1. 后端返回文件格式不是 utf-8 解决方案:后端加 2. 若添加 utf-8 后依旧乱码 请求配置中添加 responseType: arraybuffer, export function downMode() {return http.request({url: baseUrl downTemplate,method: get,responseType: arraybuffer,}); }下载 con…...
Linux/Windows 系统分区
1. Windows 系统 1.1 系统分区 系统分区也叫做磁盘分区,即分盘; 举个例子,好比家里有一个大柜子,把衣服,鞋子,袜子都放在里面,由于没有隔断,找的时候非常麻烦,找是能找…...
C/C++ xml库
文章目录 一、介绍1.1 xml 介绍1.2 xml 标准1.3 xml 教程1.4 xml 构成 二、C/C xml 库选型2.1 选型范围2.2 RapidXML2.3 tinyxml22.4 pugixml2.5 libxml 五、性能比较5.1 C xml 相关的操作有哪些5.2 rapidxml、Pugixml、TinyXML2 文件读取性能比较 六、其他问题6.1 version和 e…...
UniVue@v1.5.0版本发布:里程碑版本
前言 以后使用UniVue都推荐使用1.5.0以后的版本,这个版本之后,更新的速度将会放缓。 希望这个框架能够切实的帮助大家更好的开发游戏,做出一款好游戏!本开源项目采用的开源协议为MIT协议,完全开源化,以后也…...
在 Windows 上开发.NET MAUI 应用_2.生成你的第一个应用
先决条件 Visual Studio 2022 17.8 或更高版本,并安装了 .NET Multi-platform App UI 工作负载。 可参考上一篇文章:http://t.csdnimg.cn/n38Yy 创建应用 1.启动 Visual Studio 2022。 在开始窗口中,单击“创建新项目”以创建新项目&#…...
配置SMTP服务器的要点是什么?有哪些限制?
配置SMTP服务器安全性如何保障?如何高效配置服务器? SMTP作为电子邮件发送的核心协议,其配置对于确保邮件的成功传递和安全至关重要。AokSend将详细介绍配置SMTP服务器的关键要点,帮助读者建立一个高效、安全的邮件发送系统。 配…...
图形渲染基础-Unity渲染管线介绍
Unity中的渲染管线渲染场景主要分为三个阶段 剔除(Culling) 剔除摄像机不可见对象(视锥体剔除Frustum Culling)和被遮挡对象(遮挡剔除Occlusion Culling)。 渲染(Rendering) 将可见…...
junit mockito service
service类单元测试可以有两种方式 1、使用Autowired启用上下文的Bean走业务逻辑,适用于debug调试 2、使用InjectMocks不启用上下文依懒的Bean采用打桩的形式 打桩注意:service通常业务逻辑复杂,Bean的依懒层次可能很深,初用者常…...
k8s学习——升级后的k8s使用私有harbor仓库
升级后的k8s使用了第三方的容器管理器,安装了nerdctl工具来替代docker进行镜像管理。但是使用docker build打包并上传至harbor仓库的镜像,在部署过程中始终拉不下来,报错证书错误。通过journalctl -xe |grep kubelet 或 journalctl -xe |grep…...
Blender4.2版本正式上线,新版本的5个主要功能!
Blender刚刚推出了备受瞩目的 Blender 4.2 版本,这款软件专为那些在视觉特效、动画制作、游戏开发和可视化设计领域工作的艺术家们量身打造。作为最新的长期稳定更新,Blender 4.2 不仅稳定可靠,还引入了备受期待的“Eevee Next”实时渲染引…...
【python基础】基本数据类型
文章目录 一. Python基本数据类型1. 整数1.1. python的四种进制1.2. 数中的下划线 2. 浮点数3. 复数4. 布尔型5. 运算符5.1. 算术运算符5.2. 比较运算符5.3. 逻辑运算符5.4 运算符优先级 6. 常量 二. 注释三. Python之禅 一. Python基本数据类型 1. 整数 无长度限制࿱…...
关于腾讯广告算法大赛2025项目分析1 - dataset.py
把原始 jsonl 用户行为序列,转成模型能直接吃的张量tensor和特征字典 一、整体定位 MyDataset 读取训练数据,产出: 用户序列 seq正样本 pos负样本 negtoken 类型各类特征时间特征相关原始时间戳 MyTestDataset 读取测试/推理数据,产出 用户序…...
OpenClaw快速安装部署:让AI住进你的电脑
一、前言 上篇说完OpenClaw是什么,有小伙伴留言说:“听起来挺猛,但安装肯定很复杂吧?”确实,之前我也有这个顾虑。毕竟涉及到Gateway、Agent、多渠道配置,听起来就头大。 但实际搞下来——就两条命令。 今天…...
Llama-3.2V-11B-cot开发者案例:基于Streamlit定制化UI扩展实践
Llama-3.2V-11B-cot开发者案例:基于Streamlit定制化UI扩展实践 1. 项目概述 Llama-3.2V-11B-cot是一款基于Meta Llama-3.2V-11B-cot多模态大模型开发的高性能视觉推理工具。该工具针对双卡4090环境进行了深度优化,特别修复了视觉权重加载的关键问题&am…...
Spigot服务器搭建后,别忘了做这5件事:优化、备份、插件与安全基础设置
Spigot服务器搭建后必做的5项关键优化与安全设置 当你第一次看到Spigot服务器成功启动时,那种成就感确实令人兴奋。但很快你会发现,一个能运行的基础服务器和真正稳定、高效、安全的游戏环境之间,还有不小的距离。很多新手服主在这个阶段容易…...
保姆级教程:在Jeecg-Vue3项目中快速集成SuperQuery高级查询组件(含完整配置代码)
Jeecg-Vue3项目实战:SuperQuery高级查询组件深度集成指南 在后台管理系统开发中,高效的数据筛选功能直接影响用户体验和操作效率。Jeecg-Vue3作为企业级快速开发框架,其内置的SuperQuery组件能够帮助开发者快速构建复杂的多条件查询面板。本文…...
3大创新突破:FlashPatch如何让Flash内容重获新生
3大创新突破:FlashPatch如何让Flash内容重获新生 【免费下载链接】FlashPatch FlashPatch! Play Adobe Flash Player games in the browser after January 12th, 2021. 项目地址: https://gitcode.com/gh_mirrors/fl/FlashPatch 如何解决2021年后Flash内容无…...
基于Matlab的大气信道仿真:MIE理论在雨中光衰减计算的实践
152.基于matlab的大气信道的仿真程序。 MIE理论计算光在雨中的衰减。 前项递推法或者直接计算贝塞尔函数在计算雨这种吸收性大颗粒,自变量太大而产生溢出,限制mie计算范围,用MIE散射理论,计算单球粒子对平面光波的散射。 程序已调…...
Python零基础到入门-数据类型的内置方法(1)
当我们在操作 字符串/列表,要想到对字符串或者列表做一些高级的操作字符串 判断这个字符是否以 某个字符开头列表 添加元素 删除元素 修改元素 。。。官方根据上边的功能,给我们提供了一些公共的接口(方法)【一】整数类型语法&…...
VIIRS在灾害监测中的实战应用:以洪水检测为例的Python代码解析
VIIRS在灾害监测中的实战应用:以洪水检测为例的Python代码解析 当洪水席卷城镇时,每一分钟的响应延迟都可能意味着更多生命财产的损失。VIIRS(可见光红外成像辐射计套件)作为NASA灾害监测系统的"鹰眼",其375…...
【实战教程】OpenClaw从零开始配置指南:从边界到稳定的分层配置策略
本文适合从零开始,慢慢养、安全的养小龙虾的达人们。 更深入的调优配置请参考:Openclaw高阶调优之配置篇、OpenClaw高阶调优之模型(tokens)篇 核心理念 OpenClaw 配置的核心不是堆砌字段,而是对系统边界的精准管控。…...
