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

力扣爆刷第77天--动态规划一网打尽打家劫舍问题

力扣爆刷第77天–动态规划一网打尽打家劫舍问题

文章目录

      • 力扣爆刷第77天--动态规划一网打尽打家劫舍问题
      • 一、198.打家劫舍
      • 二、213.打家劫舍II
      • 三、337.打家劫舍 III

一、198.打家劫舍

题目链接:https://leetcode.cn/problems/house-robber/
思路:小偷不能连续两家偷,由此可以定义dp[i]表示,小偷经过[0,i]所能获取到的最大金额,那么我们可以得到递推公式:
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
即如果偷nums[i]家就不能偷前一家,为dp[i-2]+nums[i],如果不偷当前这家,那金额就要维持为经过前一家时的结果。
很简单的题目,标准的动态规划,进行状态选择。
标准写法

class Solution {public int rob(int[] nums) {if(nums.length == 1) return nums[0];int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for(int i = 2; i < nums.length; i++) {dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);}return dp[nums.length-1];}
}

优化写法

class Solution {public int rob(int[] nums) {if (nums.length == 1) return nums[0];int a = nums[0], b= Math.max(nums[0], nums[1]);for (int i = 2; i < nums.length; i++) {int c = Math.max(b, a+nums[i]);a = b;b = c;}return b;}
}

二、213.打家劫舍II

题目链接:https://leetcode.cn/problems/house-robber-ii/
思路:本题和上一题不同之处是房间首尾相连,那么也很简单,直接从两个范围求,第一个范围[0, len-1], 第二个范围[1, len],分别从这两个范围,一个只含头,一个只含尾,其他的和上一题一样。

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(getMax(nums, 0, nums.length-1), getMax(nums, 1, nums.length));}int getMax(int[] nums, int s, int e) {int[] dp = new int[nums.length];dp[s] = nums[s];dp[s+1] = Math.max(nums[s], nums[s+1]);for(int i = s+2; i < e; i++) {dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);}return dp[e-1];}
}

三、337.打家劫舍 III

题目链接:https://leetcode.cn/problems/house-robber-iii/description/
思路:二叉树形态的打家劫舍,其实也很简单,每个节点有两种状态分别是抢不与抢,后序遍历返回dp数组,有了左右子树的dp数组即可计算当前节点的dp数组,计算后返回,以此递归即可解题。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int rob(TreeNode root) {int[] dp = traverse(root);return Math.max(dp[0], dp[1]);}// 0 偷 1 不偷int[] traverse(TreeNode root) {if(root == null) return new int[2];int[] left = traverse(root.left);int[] right = traverse(root.right);int[] dp = new int[2];dp[0] = root.val + left[1] + right[1];dp[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);return dp;      }}

相关文章:

力扣爆刷第77天--动态规划一网打尽打家劫舍问题

力扣爆刷第77天–动态规划一网打尽打家劫舍问题 文章目录 力扣爆刷第77天--动态规划一网打尽打家劫舍问题一、198.打家劫舍二、213.打家劫舍II三、337.打家劫舍 III 一、198.打家劫舍 题目链接&#xff1a;https://leetcode.cn/problems/house-robber/ 思路&#xff1a;小偷不…...

深入理解C语言(5):程序环境和预处理详解

文章主题&#xff1a;程序环境和预处理详解&#x1f30f;所属专栏&#xff1a;深入理解C语言&#x1f4d4;作者简介&#xff1a;更新有关深入理解C语言知识的博主一枚&#xff0c;记录分享自己对C语言的深入解读。&#x1f606;个人主页&#xff1a;[₽]的个人主页&#x1f3c4…...

ESP8266智能家居(3)——单片机数据发送到mqtt服务器

1.主要思想 前期已学习如何用ESP8266连接WIFI&#xff0c;并发送数据到服务器。现在只需要在单片机与nodeMCU之间建立起串口通信&#xff0c;这样单片机就可以将传感器测到的数据&#xff1a;光照&#xff0c;温度&#xff0c;湿度等等传递给8266了&#xff0c;然后8266再对数据…...

lvm逻辑卷创建raid阵列(不常用)—— 筑梦之路

RAID卷介绍 逻辑卷管理器(LVM)不仅仅可以将多个磁盘和分区聚合到一个逻辑卷中&#xff0c;以此提高单个分区的存储容量&#xff0c;还可以创建和管理独立磁盘的冗余阵列(RAID)卷&#xff0c;防止磁盘故障并提高性能。它支持常用的RAID级别&#xff0c;支持的RAID的级别有 0、1…...

LayUI发送Ajax请求

页面初始化操作 var processData null $(function () {initView();initTable();// test(); })function initView() {layui.use([laydate, form], function () {var laydate layui.laydate;laydate.render({elem: #applyDateTimeRange,type: datetime,range: true});}); }初始…...

平时积累的FPGA知识点(10)

平时在FPGA群聊等积累的FPGA知识点&#xff0c;第10期&#xff1a; 41 ZYNQ系列芯片的PL中使用PS端送过来的时钟&#xff0c;这些时钟名字是自动生成的吗&#xff1f; 解释&#xff1a;是的。PS端设置的是ps_clk&#xff0c;用report_clocks查出来的时钟名变成了clk_fpga_0&a…...

使用Streamlit构建纯LLM Chatbot WebUI傻瓜教程

文章目录 使用Streamlit构建纯LLM Chatbot WebUI傻瓜教程开发环境hello Streatelit显示DataFrame数据显示地图WebUI左右布局设置st.sidebar左侧布局st.columns右侧布局 大语言模型LLM Chatbot WebUI设置Chatbot页面布局showdataframe()显示dataframeshowLineChart()显示折线图s…...

电脑死机卡住怎么办 电脑卡住鼠标也点不动的解决方法

在我们使用电脑的过程中,可能由于电脑硬件或者软件的问题,偶尔会出现电脑卡住的情况,很多电脑小白都不知道电脑卡住了怎么办,鼠标也点不动,键盘也没用,一旦发生了这种情况,大家可以来参考一下小编分享的电脑死机卡住的解决方法。 电脑卡住鼠标也点不动的解决方法 方…...

RAG 语义分块实践

每日推荐一篇专注于解决实际问题的外文,精准翻译并深入解读其要点,助力读者培养实际问题解决和代码动手的能力。 原文标题:Semantic chunking in practice 原文地址:https://medium.com/@boudhayan-dev/semantic-chunking-in-practice-23a8bc33d56d 语义分块的实践 回顾 …...

12 Autosar_SWS_MemoryMapping.pdf解读

AUTOSAR中MemMap_autosar memmap-CSDN博客 1、Memory Map的作用 1.1 避免RAM的浪费&#xff1a;不同类型的变量&#xff0c;为了对齐造成的空间两份&#xff1b; 1.2 特殊RAM的用途&#xff1a;比如一些变量通过位掩码来获取&#xff0c;如果map到特定RAM可以通过编译器的位掩码…...

【Linux取经路】文件系统之缓冲区

文章目录 一、先看现象二、用户缓冲区的引入三、用户缓冲区的刷新策略四、为什么要有用户缓冲区五、现象解释六、结语 一、先看现象 #include <stdio.h> #include <string.h> #include <unistd.h>int main() {const char* fstr "Hello fwrite\n"…...

华为OD机试真题-查找接口成功率最优时间段-2023年OD统一考试(C卷)--Python3--开源

题目&#xff1a; 考察内容&#xff1a; for 时间窗口list(append, sum, sort) join 代码&#xff1a; """ 题目分析&#xff1a;最长时间段 且平均值小于等于minLost同时存在多个时间段&#xff0c;则输出多个&#xff0c;从大到小排序未找到返回 NULL 输入…...

缓存篇—缓存雪崩、缓存击穿、缓存穿透

缓存异常会面临的三个问题&#xff1a;缓存雪崩、击穿和穿透。 其中&#xff0c;缓存雪崩和缓存击穿主要原因是数据不在缓存中&#xff0c;而导致大量请求访问了数据库&#xff0c;数据库压力骤增&#xff0c;容易引发一系列连锁反应&#xff0c;导致系统奔溃。不过&#xff0…...

Python实现视频转音频、音频转文本的最佳方法

文章目录 Python实现视频转音频和音频转文字视频转音频步骤 1&#xff1a;导入moviepy库步骤 2&#xff1a;选择视频文件步骤 3&#xff1a;创建VideoFileClip对象步骤 4&#xff1a;提取音频步骤 5&#xff1a;保存音频文件 音频转文字步骤 1&#xff1a;导入SpeechRecognitio…...

阿里云SSL免费证书到期自动申请部署程序

阿里云的免费证书只有3个月的有效期&#xff0c;不注意就过期了&#xff0c;还要手动申请然后部署&#xff0c;很是麻烦&#xff0c;于是写了这个小工具。上班期间抽空写的&#xff0c;没有仔细测试&#xff0c;可能存在一些问题&#xff0c;大家可以自己clone代码改改&#xf…...

Vue全局事件防止重复点击(等待请求)【进阶版】

继《Vue全局指令防止重复点击&#xff08;等待请求&#xff09;》之后&#xff0c;感觉指令方式还是不太友好&#xff0c;而且嵌套闭包比较麻烦&#xff0c;于是想到了Vue的全局混入&#xff0c;利用混入&#xff0c;给组件绑定click事件。 一、实现原理 与指令方式大致一样&…...

C#程序反编译经验总结

1. 反编译出的代码有问题时&#xff0c;可以用多个反编译工具之间的代码相互印证。&#xff08;比如.net reflector 与ILSpy&#xff09; 2. 有时Visual Studio编译的错误信息不明确时, 可以msbuild编译程序&#xff0c;msbuild的错误信息相对完整一些。 2.1 编译错误&#xf…...

Android系统启动流程

android的启动流程是从底层开始进行的&#xff0c;具体如下所示&#xff1a; Android是基于Linux内核的系统&#xff0c;Android的启动过程主要分为两个阶段&#xff0c;首先是Linux内核的启动&#xff0c;然后是Android框架的启动。 可以将Andorid系统的启动流程分为以下五个…...

Flask——基于python完整实现客户端和服务器后端流式请求及响应

文章目录 本地客户端Flask服务器后端客户端/服务器端流式接收[打字机]效果 看了很多相关博客&#xff0c;但是都没有本地客户端和服务器后端的完整代码示例&#xff0c;有的也只说了如何流式获取后端结果&#xff0c;基本没有讲两端如何同时实现流式输入输出&#xff0c;特此整…...

crmeb多门店商城系统二次开发 增加车辆车牌搜索功能、车辆公里数

1、增加的数据库 ALTER TABLE eb_store_order ADD cart_number VARCHAR(255) NOT NULL DEFAULT COMMENT 车牌 AFTER erp_order_id, ADD curmileage VARCHAR(255) NOT NULL DEFAULT COMMENT 当前里程 AFTER cart_number; ALTER TABLE eb_store_cart ADD cart_number VARCHAR(…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...