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

leetcode 刷题day38动态规划Part07 打家劫舍(198.打家劫舍、213.打家劫舍II、337.打家劫舍III)

198.打家劫舍

思路:
1、dp[i]为到第i家偷到的最高金额。
2、如果偷第i家,那么dp[i]=dp[i-2]+nums[i],如果不偷,则dp[i]=dp[i-1],所以递推公式dp[i]=max(dp[i-2]+nums[i],dp[i-1])。
3、初始值,根据递推公式,我们需要知道dp[0]和dp[1]。dp[0]=nums[0], dp[1]=max(nums[0],nums[1]);
4、遍历顺序为从小到大遍历nums[i]。

代码如下:

class Solution {public int rob(int[] nums) {if(nums==null || nums.length==0) return 0;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];}
}

213.打家劫舍II

思路:该题与上一题的区别在于第一个和最后一个房屋相邻。有两种情况:只考虑打劫第1家到倒数第2家;只考虑打劫第2家到最后一家。

代码如下:

class Solution {public int rob(int[] nums) {int len=nums.length;if(nums==null || len==0) return 0;if(len==1) return nums[0];return Math.max(robAction(nums,0,len-1),robAction(nums,1,len));}public int robAction(int[] nums, int start, int end){int x=0,y=0,z=0;for(int i=start;i<end;i++){z=Math.max(x+nums[i],y);x=y;y=z;}return z;}
}

337.打家劫舍III

思路:记录树上每个节点状态的变化,使用一个长度为2的数组,记录当前节点偷与不偷所得到的的最大金钱。

以递归三部曲为框架,融合动规五部曲的进行分析。

1、确定递归函数的参数和返回值
传入参数为当前节点,返回值是一个长度为2的数组。
即dp数组(dp table)以及下标的含义:下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱。

2、确定终止条件
空节点无论偷还是不偷都是0,所以返回0。
相当于dp数组的初始化。

3、确定遍历顺序
使用后序遍历, 因为要通过递归函数的返回值来做下一步计算。
通过递归左节点,得到左节点偷与不偷的金钱。
通过递归右节点,得到右节点偷与不偷的金钱。

4、确定单层递归的逻辑
如果是偷当前节点,那么左右孩子就不能偷,val1 = cur->val + left[0] + right[0];
如果不偷当前节点,那么左右孩子就可以偷,至于到底偷不偷一定是选一个最大的,所以:val2 = max(left[0], left[1]) + max(right[0], right[1]);

当前节点的状态就是{val2, val1}; 即:{不偷当前节点得到的最大金钱,偷当前节点得到的最大金钱}

5、举例推导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[] res=robAction(root);return Math.max(res[0],res[1]);}public int[] robAction(TreeNode root){int[] res=new int[2];if(root==null) return res;int[] left=robAction(root.left);int[] right=robAction(root.right);res[1]=root.val+left[0]+right[0];res[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);return res;}
}

相关文章:

leetcode 刷题day38动态规划Part07 打家劫舍(198.打家劫舍、213.打家劫舍II、337.打家劫舍III)

198.打家劫舍 思路&#xff1a; 1、dp[i]为到第i家偷到的最高金额。 2、如果偷第i家&#xff0c;那么dp[i]dp[i-2]nums[i],如果不偷&#xff0c;则dp[i]dp[i-1]&#xff0c;所以递推公式dp[i]max(dp[i-2]nums[i],dp[i-1])。 3、初始值&#xff0c;根据递推公式&#xff0c;我们…...

C0010.Qt5.15.2下载及安装方法

1. 下载及安装 Qt 添加链接描述下载地址&#xff1a;http://download.qt.io/ 选择 archive 目录 安装Qt **注意&#xff1a;**本人使用的是Qt5.15.2版本&#xff0c;可以按如下方法找到该版本&#xff1b;...

制造企业MES管理系统的应用策略与实施路径

在智能制造浪潮的席卷之下&#xff0c;MES管理系统作为连接生产计划与车间操作的核心桥梁&#xff0c;其战略地位愈发显著。本文旨在深入剖析MES管理系统在智能制造转型中的核心价值、实施策略及实践路径&#xff0c;为制造企业探索智能化生产之路提供实践指导与灵感启发。 MES…...

Halcon 3D应用 - 胶路提取

1. 需求 本文基于某手环&#xff08;拆机打磨处理&#xff09;做的验证性工作&#xff0c;为了项目保密性&#xff0c;只截取部分数据进行测试。 这里使用的是海康3D线激光轮廓相机直线电机的方式进行的高度数据采集&#xff0c;我们拿到的是高度图亮度图数据。 提取手环上的胶…...

【Redis】Redis线程模型

目录 1. Redis 是单线程的&#xff0c;还是多线程的&#xff1f;2. Redis单线程模式是怎么样的&#xff1f;Redis 单线程模式的优势Redis 单线程的局限性Redis 单线程的优化策略 3. Redis采用单线程为什么还这么快4. Redis 6.0 之前为什么使用单线程&#xff1f;5. Redis 6.0 之…...

Electron构建桌面应用程序,服务于项目的自主学习记录(持续更新...

无所畏惧地面对未知&#xff0c;并将其视为成长的机会 大纲官网快速入门1.安装node.js -- 这里推荐用nvm管理2.脚手架创建3.electron 包安装到应用的开发依赖4.创建主进程(main.js)并启动项目1.创建页面2.配置main.js3.启动项目 -- 效果 进阶 -- 基于项目场景功能使用场景一&am…...

linux Load Average 计算

在内核代码 kernel/sched/loadavg.c 中有一个公式: a1 a0 * e a * (1 - e) 此算法是指数加权移动平均法&#xff08;Exponential Weighted Moving Average&#xff0c;EMWA&#xff09;&#xff0c;是一种特殊的加权移动平均法&#xff0c;它考虑当前和历史的所有数据&#…...

pandas常用数据格式IO性能对比

前言 本文对pandas支持的一些数据格式进行IO&#xff08;读写&#xff09;的性能测试&#xff0c;大数据时代以数据为基础&#xff0c;经常会遇到操作大量数据的情景&#xff0c;数据的IO性能尤为重要&#xff0c;本文对常见的数据格式csv、feather、hdf5、jay、parquet、pick…...

【D3.js in Action 3 精译_031】3.5.2 DIY实战:在 Observable 平台实现带数据标签的 D3 条形图并改造单元测试模块

当前内容所在位置&#xff08;可进入专栏查看其他译好的章节内容&#xff09; 第一部分 D3.js 基础知识 第一章 D3.js 简介&#xff08;已完结&#xff09; 1.1 何为 D3.js&#xff1f;1.2 D3 生态系统——入门须知1.3 数据可视化最佳实践&#xff08;上&#xff09;1.3 数据可…...

华为OD机试真题-字符串分割

题目描述&#xff1a; 给定非空字符串s&#xff0c;将该字符串分割成一些子串&#xff0c;使每个子串的ASCII码值的和均为水仙花数。 1、若分割不成功&#xff0c;则返回0。 2、若分割成功且分割结果不唯一&#xff0c;则返回-1。 3、若分割成功且分割结果唯一&#xff0c;则返…...

编程技巧:提高代码健壮性与可维护性的关键方法(以 Shell 为例)

在脚本编写和自动化工作中,良好的编程技巧对于确保代码的健壮性和可维护性至关重要。以下是一些关键的编程技巧,包括模块化设计、单元测试、版本控制、处理边界条件、错误处理、中间值保存和创建 Flag。本文将通过 Shell 脚本示例来阐述这些技巧的应用。 1. 模块化设计 **定…...

【无标题】ReadableStream is not defined

升级 node 版本到 18 及以上即可解决...

【JVM】高级篇

1 GraalVM 1.1 什么是GraalVM GraalVM是Oracle官方推出的一款高性能JDK&#xff0c;使用它享受比OpenJDK或者OracleJDK更好的性能。 GraalVM的官方网址&#xff1a;https://www.graalvm.org/ 官方标语&#xff1a;Build faster, smaller, leaner applications。 更低的CPU…...

nacos1.4源码-服务发现、心跳机制

nacos的服务发现主要采用服务端主动推送客户端定时拉取&#xff1b;心跳机制通过每5s向服务端发送心跳任务来保活&#xff0c;当超过15s服务端未接收到心跳任务时&#xff0c;将该实例设置为非健康状态&#xff1b;当超过30s时&#xff0c;删除该实例。 1.服务发现 nacos主要采…...

C++ 2D平台游戏开发案例

关于2D平台游戏的C开发案例&#xff0c;包括游戏设计、实现细节、图形渲染和音效处理等内容。虽然无法一次性提供3000字&#xff0c;但我会尽量详细描述各个部分&#xff0c;并确保有足够的深度和广度。 2D平台游戏开发案例 一、游戏设计 游戏概述 游戏名称&#xff1a;“冒险…...

【Webpack--019】TreeShaking

&#x1f913;&#x1f60d;Sam9029的CSDN博客主页:Sam9029的博客_CSDN博客-前端领域博主 &#x1f431;‍&#x1f409;若此文你认为写的不错&#xff0c;不要吝啬你的赞扬&#xff0c;求收藏&#xff0c;求评论&#xff0c;求一个大大的赞&#xff01;&#x1f44d;* &#x…...

Docker基本操作命令

Docker 是一个开源的应用容器引擎&#xff0c;允许开发者打包应用以及其依赖包到一个可移植的容器中&#xff0c;然后发布到任何流行的 Linux 机器上&#xff0c;也可以实现虚拟化。容器是完全使用沙箱机制&#xff0c;相互之间不会有任何接口。主要功能是为开发者提供一个简单…...

开源计算器应用的全面测试计划:确保功能性和可靠性

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

uni.requestPayment 支付成功之后会走 wx.onAppRoute

uni.requestPayment 是用于发起微信支付的统一接口&#xff0c;而 wx.onAppRoute 是用于监听小程序的路由变化。当 uni.requestPayment 支付成功后&#xff0c;如果发生了页面跳转或者其他路由变化&#xff0c;wx.onAppRoute 会被触发。这个行为是正常的&#xff0c;因为支付成…...

统⼀服务入口 - Gateway

网关介绍 问题 在 spring cloud 体系中我们通过 Eureka,Nacos 解决了服务注册,服务发现的问题,使⽤Spring Cloud LoadBalance解决了负载均衡的问题,使⽤ OpenFeign 解决了远程调⽤的问题. 但是当前所有微服务的接⼝都是直接对外暴露的,可以直接通过外部访问.为了保证对外服务的…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...