【LeetCode】【算法】198. 打家劫舍

LeetCode 198. 打家劫舍

题目描述

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

思路

因为不能偷相邻的房间,假设当前这间必偷,其他的要么偷第n-2间,要么偷第n-3
动态规划求解,dp数组含义为偷窃当前房屋能够获得的最高金额
初始化:dp数组初始化为0,dp[0]初始化为nums[0]dp[1]初始化为nums[1]dp[2]的取值为Math.max(dp[0]+nums[2], dp[1])
动态求解:for循环从3开始,dp[i]=Math.max(dp[i-2]+nums[i], dp[i-3] + nums[i])
最高金额记录:定义变量max,if (max > dp[i]) max = dp[i]

代码

class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0){return 0;}else if (nums.length == 1){return nums[0];}else if (nums.length == 2){return Math.max(nums[0], nums[1]);}int[] dp = new int[nums.length];// 初始化dpdp[0] = nums[0];dp[1] = nums[1];dp[2] = Math.max(dp[1], dp[0] + nums[2]);if (nums.length == 3){return dp[2];}int cur_max = dp[2];// 正式对dp做操作for (int i = 3; i < dp.length; i++) {dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 3] + nums[i]);if (dp[i] > cur_max){cur_max = dp[i];}}return cur_max;}
}

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

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

相关文章

爱回收根关键字获取对应品牌的ID API 返回值深入解析

在数字化时代&#xff0c;二手商品交易市场日益繁荣&#xff0c;其中爱回收作为一个重要的平台&#xff0c;提供了一个便捷的接口&#xff0c;使得开发者能够通过API获取对应品牌的ID。本文将详细介绍如何使用爱回收的API&#xff0c;通过根关键字来获取品牌ID&#xff0c;并提…

给自己域名生成tls证书并在服务器进行配置

背景 自己搭建的服务器&#xff0c;使用https访问时会报不安全&#xff0c;给人一种不靠谱的赶脚&#xff0c;于是乎&#xff0c;决定使用个免费的方式来配置个证书解决这个问题 解决 首先需要有自己的公网域名&#xff0c;我的是某里云购买的,如何购买域名这里不聊 需要一…

java反序列化学习之CommonCollections3利用链的学习

一、前言 在前文中&#xff0c;我们学习了Java的类加载过程&#xff0c;类加载器以及Java中加载字节码的一些方法&#xff0c;其中介绍了TemplatesImpl&#xff0c;TemplatesImpl是一个可以加载字节码的类&#xff0c;通过调用其newTransformer()方法&#xff0c;即可执行这段字…

钨酸铵溶液净化除钾钠杂质

钨酸铵溶液的主要用途包括制造三氧化钨、蓝色氧化钨、偏钨酸铵及其他钨化合物&#xff0c;以及作为石油化工行业的添加剂‌‌ 制造其他钨化合物&#xff1a; 钨酸铵溶液可以用于制造三氧化钨或蓝色氧化钨&#xff0c;这些化合物进一步用于生产金属钨粉。金属钨粉是制造钨条、钨…

线程安全的单例模式

单列模式是校考中最常考的设计模式之一 啥是设计模式&#xff1f; 设计模式就好比好比向其中的“棋谱”&#xff0c;红方当头炮&#xff0c;黑方马来跳。针对红方的一些走法黑方有一些固定的套路。按照套路来走局势就不会吃亏。 软件开发中有很对常见的“问题场景‘&#xff1a…

【云岚到家】-day09-1-项目迁移6-秒杀抢购介绍

【云岚到家】-day09-1-项目迁移6-秒杀抢购介绍 1 购物车1.1 交互流程1.2 Redis数据结构1.3 表设计1.4 定时同步购物车 2 签到活动2.1 需求分析2.2 系统设计2.2.1 表设计2.2.2 接口设计2.2.3 如何计算连续签到天数2.2.4 如何获取匹配签到奖励规则2.2.5 签到代码 3 秒杀抢购介绍1…

探索LINQ在C#中的应用:从基本查询到数据联接

LINQ&#xff08;语言集成查询&#xff09;是微软为.NET框架开发的一种强大功能&#xff0c;于2007年作为C# 3.0和Visual Basic .NET 9.0的一部分引入。LINQ的诞生旨在提供一种一致且直观的方式来查询和操作数据&#xff0c;无论数据来源是内存中的集合、数据库还是XML文档。 …

FileLink如何帮助医疗行业实现安全且高效的跨网文件交换

在当今数字化时代&#xff0c;医疗行业在快速发展的同时&#xff0c;也面临着数据安全和信息流转效率的双重挑战。患者的健康记录、影像数据、检查报告等大量敏感信息需要在不同医院、诊所、实验室和保险公司之间高效、迅速地传递。然而&#xff0c;传统的邮件、传真和纸质文件…

windows工具 -- 一个定时播放音乐并延迟锁屏的bat脚本(专注模式) 每隔45分钟电脑自动锁屏

目的 由于静脉曲张比较难受, 不能长时间坐着, 需要有一个强迫休息的功能: 工作45分钟45分钟到了, 自动播放音乐, 并提示30s后进行锁屏 创建bat脚本 创建一个 .txt 文本文件, 然后修改后缀名为 .bat 右键记事本打开, 复制以下代码保存 echo off :: 等待45分钟 TIMEOUT /T 2700…

opencv_相关的问题

Debug模型下运行&#xff0c;在命令行窗口会有一些error相关的log信息。 通过调整log的等级&#xff0c;屏蔽掉INFO的log信息 #include <opencv2/core/utils/logger.hpp>cv::utils::logging::setLogLevel(cv::utils::logging::LOG_LEVEL_ERROR);

深度学习-44-大模型预训练的数据预处理及大模型的分类

文章目录 1 大模型的分类1.1 按任务类型分类1.1.1 生成式模型1.1.2 判别式模型1.1.3 混合模型1.2 按数据模态分类1.2.1 单模态模型1.2.2 多模态模型1.3 按训练方法分类1.3.1 预训练模型1.3.2 从零训练模型1.3.3 迁移学习模型1.4 按应用领域分类1.4.1 自然语言处理模型1.4.2 计算…

zabbix安装基础配置

服务器准备&#xff0c;两台服务器 创建zabbix用户组&#xff0c;新增zabbix用户&#xff0c;并将zabbix用户加入zabbix用户组&#xff0c;设置zabbix用户不允许登录系统权限 [rootlocalhost ~]# groupadd zabbix [rootlocalhost ~]# useradd -g zabbix zabbix [rootlocalhost…

点云的多尺度计算

1.计算点云多尺度特征的方法 1) K近邻,然后通过VoxelGrid进行下采样。 参考文献: Timo Hackel, J. D. W., Konrad Schindler "FAST SEMANTIC SEGMENTATION OF 3D POINT CLOUDS WITH STRONGLY VARYING DENSITY." Schindler, T. H. J. D. W. K. "Contour dete…

如何将各类GIS格式数据转换为带坐标信息的CVS或EXCEL格式

介绍如何利用GIS数据转换器-矢量将各类GIS格式数据&#xff08;SHP\TAB\KML\GEOJSON\GPKG\dxf等&#xff09;转换为带坐标信息的CVS或EXCEL格式。 打开GIS数据转换器-矢量 2.选择要转换的矢量数据 3.选择要输出的格式为CSV或微软开放表格格式 4.选择输出字段 5.选择输出目录 6…

Latex之LNCS模板——Title Suppressed Due to Excessive Length

1、问题描述 使用LNCS模板时&#xff0c;文章右上角显示“Title Suppressed Due to Excessive Length”。原因&#xff1a;文章的标题太长&#xff0c;放不下。 2、解决办法 使用 \titlerunning{} 设置一个短标题。

DPI-MoCo:基于深度先验图像约束的运动补偿重建用于四维锥形束CT (4D CBCT)|文献速递-基于深度学习的病灶分割与数据超分辨率

Title 题目 DPI-MoCo: Deep Prior Image ConstrainedMotion Compensation Reconstruction for 4D CBCT DPI-MoCo&#xff1a;基于深度先验图像约束的运动补偿重建用于四维锥形束CT (4D CBCT) 01 文献速递介绍 安装在直线加速器上的N板锥束计算机断层扫描&#xff08;CBCT&…

6大国有银行软开的薪资待遇清单

牛客上刷到一条关于计算机专业值得去的银行软开清单,其中对 6 大国有银行软开的薪资待遇分析我觉得很有必要同步给大家看一看。 截图信息来自牛客的漫长白日梦 其中邮储软开是最值得推荐的(offer 投票没输过),二线城市转正后第一个完整年的收入在 30 万左右,一线城市更高…

深度学习之Dropout

1 Dropout 系列问题 1.1 为什么要正则化&#xff1f; 深度学习可能存在过拟合问题——高方差&#xff0c;有两个解决方法&#xff0c;一个是正则化&#xff0c;另一个是准备更多的数据&#xff0c;这是非常可靠的方法&#xff0c;但你可能无法时时刻刻准备足够多的训练数据或…

京东AI单旋旋转验证码98准确率通杀方案

注意,本文只提供学习的思路,严禁违反法律以及破坏信息系统等行为,本文只提供思路 如有侵犯,请联系作者下架 本文滑块识别已同步上线至OCR识别网站: http://yxlocr.nat300.top/ocr/other/12 京东单旋验证码最近更新了,使用AI生成,要求识别角度,以下是部分数据集: 接下…

three.js 如何简单的实现场景的雾

three.js 如何简单的实现场景的雾 https://threehub.cn/#/codeMirror?navigationThreeJS&classifybasic&idsceneFog import * as THREE from three import { OrbitControls } from three/examples/jsm/controls/OrbitControls.js import { GLTFLoader } from three…