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

一篇文章带你用动态规划解决打家劫舍问题

动态规划的解题步骤可以分为以下五步,大家先好好记住

1.创建dp数组以及明确dp数组下标的含义  2.制定递推公式  3.初始化  4.遍历顺序  5.验证结果


根据打家劫舍的题意:两个直接相连的房子在同一天晚上被打劫会触发警报

所以我们制定出核心策略——偷东西只能隔一家偷!

接下来只要记住核心思想,围绕这个思想来解题就可以了!

核心思想 :如果偷了这家那么上一家就不能偷,如果不偷这一家那么上一家就可以偷

首先看第一题

198. 打家劫舍

这是一道标准的打家劫舍问题

运用动态规划解题步骤结合核心代码来进行解题

    public int rob(int[] nums) {int n = nums.length;//dp数组下标的含义是抢劫到该房屋的最高金额int[] dp = new int[n];//递推公式:dp[i] = Math.max(nums[i-1] + dp[i-2],dp[i-1]);//初始化dp[0] = nums[0];//遍历顺序 从后向前遍历for(int i = 1;i < n;i++){if(i >= 2){dp[i] = Math.max(nums[i] + dp[i-2],dp[i-1]);}else{dp[i] = Math.max(nums[i],dp[i-1]);}}//验证return dp[n-1];}

213. 打家劫舍 II

这道题实际上是第一题的变招(看起来把屋子围起来了让小偷偷到钱财的难度增加了,但实际上小偷只需要转变一下思路也可以偷到很多钱 ^ ^ )

由于屋子围了起来,所以第一间屋子和最后一屋子现在是相邻的了

如果还是像刚才一样从头偷到尾那肯定是行不通的了。但是如果我避开这个第一间屋子和最后一屋子现在是相邻的了”这个条件是不是还是从头偷到尾呢?

答案是可以的,以题目的示例二举例

现在我们只需要指定两套方案,一套是从第一间偷到倒数第二间房子,另一套是从第二间偷到最后一间房子,然后比较两套方案哪个偷到的金额更大即可

接下来结合这个思想以及核心代码来编写代码

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

337. 打家劫舍 III

这道题还是有点难度的,既用到了动态规划又用到了二叉树的知识,但是结合上核心思想还是很简单的

根据题意两个直接相连的房子在同一天晚上被打劫结合核心思想

如果偷了孩子节点那么父节点就不能偷了,如果偷了父节点那么子节点就不能偷了

我们可以用一个二维数组来表达偷了该节点所获得的最大金额以及不偷该节点所获得最大金额

//0表示不偷该节点 1表示偷该节点
int[][] res = new int[2][1];

到这里动态规划需要解决的问题就解决了 

ok解决完动态规划的部分接下来来看二叉树的部分需要解决的问题 —— 遍历顺序

由于我们先要知道孩子节点的情况才能做出下一步判断

所以我们使用后序遍历的方式对树进行遍历

解决完两个难点接下来结合核心思想来编写代码

    public int rob(TreeNode root) {int[][] result = robHelper(root);return Math.max(result[0][0],result[1][0]);}public int[][] robHelper(TreeNode root) {//表示偷还是不偷int[][] res = new int[2][1];//遇到空节点返回if(root == null){return res;}//从底部向上遍历所以是后序遍历int[][] left = robHelper(root.left);int[][] right = robHelper(root.right);//不偷父节点所以要获取孩子节点的最大值res[0][0] = Math.max(left[0][0],left[1][0]) + Math.max(right[0][0],right[1][0]);//偷父节点所以不能偷孩子节点了res[1][0] = left[0][0] + right[0][0] + root.val;return res;}

总的来说只要结合了核心思想“偷这个就不能偷那个” 打家劫舍问题还是很简单的

相关文章:

一篇文章带你用动态规划解决打家劫舍问题

动态规划的解题步骤可以分为以下五步&#xff0c;大家先好好记住 1.创建dp数组以及明确dp数组下标的含义 2.制定递推公式 3.初始化 4.遍历顺序 5.验证结果 根据打家劫舍的题意&#xff1a;两个直接相连的房子在同一天晚上被打劫会触发警报 所以我们制定出核心策略——偷东…...

idea中导入eclipse的javaweb项目——tomact服务(保姆级别)

idea中导入eclipse的javaweb项目——tomact服务&#xff08;保姆级别&#xff09; 1. 导入项目2. Project Settings下的各种配置步骤2.1 检查/修改 jdk 的引入2.2 配置Modules-Dependencies2.2.1 删掉eclipse相关的多余配置2.2.2 删掉jar包2.2.3 添加tomcat的依赖 2.3 配置Libr…...

【开源】给ChatGLM写个,Java对接的SDK

作者&#xff1a;小傅哥 - 百度搜 小傅哥bugstack 博客&#xff1a;bugstack.cn 沉淀、分享、成长&#xff0c;让自己和他人都能有所收获&#xff01;&#x1f604; 大家好&#xff0c;我是技术UP主小傅哥。 清华大学计算机系的超大规模训练模型 ChatGLM-130B 使用效果非常牛&…...

基于Pytest+Allure+Excel的接口自动化测试框架

1. Allure 简介 简介 Allure 框架是一个灵活的、轻量级的、支持多语言的测试报告工具&#xff0c;它不仅以 Web 的方式展示了简介的测试结果&#xff0c;而且允许参与开发过程的每个人可以从日常执行的测试中&#xff0c;最大限度地提取有用信息。 Allure 是由 Java 语言开发的…...

20.2 FMC驱动SDRAM的时序初始化实现及内存测试

继续上一篇的话题&#xff0c;写到SDRAM通过CubeMx配置后&#xff0c;在工程代码编写时直接引用的是我事先写好的时序初始化、内存测试文件&#xff0c;而未对其进行详细的解释&#xff0c;所以本篇文章就来娓娓道来。不多说&#xff0c;开始吧 SDRAM的初始化流程简述 SDRAM初…...

联想电脑一键重装系统Win10操作方法

很多用户都会利用重装系统的方法&#xff0c;来解决系统崩溃、病毒感染等问题。但是&#xff0c;很多新手用户不知道联想电脑Win10系统重装的详细方法步骤&#xff0c;下面小编给大家详细介绍关于联想电脑Win10系统重装的操作方法&#xff0c;帮助大家轻松快速地完成系统的重装…...

Mysql数据库 1.概述

Mysql内容概述 1. Mysql概述 数据库相关概念&#xff1a; 名称 全称 简称 数据库 存储数据的仓库&#xff0c;数据是有组织的进行存储 …...

Qt编程,文件操作、UDP通信

目录 1、文件类 QFile 2、 UPD/TCP网络编程 1、##UDP客户端 2、##UDP服务器端 1、文件类 QFile QFile file(filename); file.exists() file.setFileName(filename1); file.fileName() file.bytesAvailable() file.size() file.copy("2.txt") file1.errorString(…...

Docker 的数据管理和Dockerfile镜像的创建

目录 Docker 的数据管理 管理 Docker 容器中数据的方式 端口映射 容器互联&#xff08;使用centos镜像&#xff09; Docker 镜像的创建 Dockerfile 操作常用的指令 编写 Dockerfile 时格式 Dockerfile 案例 Docker 的数据管理 管理 Docker 容器中数据的方式 管理 Doc…...

[python] 利用 Pydoc 快速生成整个 Python 项目的文档

如何写注释 class MyClass:"""This is a simple example class.Attributes:param1 (int): The first parameter.param2 (str): The second parameter."""def __init__(self, param1, param2):"""The constructor for MyClass.:p…...

Maven 配置指南

目录 一、配置本地存储库 二、配置并行Artifact 解析 三、安全和部署设置 四、将镜像用于存储库 五、Profiles 六、可选配置 七、Settings 八、安全性 九、工具链 Maven配置发生在3个级别&#xff1a; 项目-大多数静态配置发生在pom.xml中安装-这是为Maven安装添加的…...

第十八章 类和对象——多态

一、多态的基本概念 多态是C面向对象三大特性之一 多态分为两类 静态多态: 函数重载 和 运算符重载属于静态多态&#xff0c;复用函数名 动态多态: 派生类和虚函数实现运行时多态 静态多态和动态多态区别&#xff1a; 静态多态的函数地址早绑定 - 编译阶段确定函数地址 动…...

京东数据平台:2023年服饰行业销售数据分析

最近看到有些消费机构分析&#xff0c;不少知名的运动品牌都把“主战场”放到了冲锋衣&#xff0c;那么羽绒服市场就比较危险了。但其实羽绒服市场也有机会点可寻。 先来说冲锋衣。的确&#xff0c;从今年的销售数据以及增长情况&#xff0c;冲锋衣的确会是今年冬天的大热门品…...

Nginx proxy_set_header参数设置

一、不设置 proxy_set_header Host 不设置 proxy_set_header Host 时&#xff0c;浏览器直接访问 nginx&#xff0c;获取到的 Host 是 proxy_pass 后面的值&#xff0c;即 $proxy_host 的值&#xff0c;参考Module ngx_http_proxy_module 1 2 3 4 5 6 7 8 # cat ngx_header.c…...

如何用 ChatGPT 的 Advanced Data Analysis 帮你采集数据?

&#xff08;注&#xff1a;本文为小报童精选文章&#xff0c;已订阅小报童或加入知识星球「玉树芝兰」用户请勿重复付费&#xff09; 想采集网页数据却不会写 Python 爬虫&#xff1f;不会就不会吧&#xff0c;ChatGPT 会就可以了 &#x1f602; 问题描述 朋友最近遇到了一点儿…...

Linux运行环境搭建系列-Flink安装

Flink安装 ## 下载 https://archive.apache.org/dist/flink/flink-1.16.2 ## 解压 tar -zxvf flink-1.16.2-bin-scala_2.12.tgz && rm -rf flink-1.16.2-bin-scala_2.12.tgz ## 启动 cd flink-1.16.2/bin ## 修改/etc/hosts文件&#xff0c;把第一行的127.0.0.1改成自…...

求最大bit数(java)

题目描述 求一个int类型数字对应的二进制数字中1的最大连续数 例如3的二进制为00000011&#xff0c;最大连续2个1 数据范围:数据组数:11t15&#xff0c;11n1500000进阶: 时间复杂度: O(logn)&#xff0c;空间复杂度: O(1) 输入: 200 输出 2 说明 200的二进制表示是11001000&am…...

【Java 进阶篇】JavaScript 与 HTML 的结合方式

JavaScript是一种广泛应用于Web开发中的脚本语言&#xff0c;它与HTML&#xff08;Hypertext Markup Language&#xff09;结合使用&#xff0c;使开发人员能够创建交互式和动态的网页。在这篇博客中&#xff0c;我们将深入探讨JavaScript与HTML的结合方式&#xff0c;包括如何…...

华为云云耀云服务器L实例评测 | 实例评测使用之硬件参数评测:华为云云耀云服务器下的 Linux 磁盘目录分析神器 ncdu

华为云云耀云服务器L实例评测 &#xff5c; 实例评测使用之硬件参数评测&#xff1a;华为云云耀云服务器下的 Linux 磁盘目录分析神器 ncdu 介绍华为云云耀云服务器 华为云云耀云服务器 &#xff08;目前已经全新升级为 华为云云耀云服务器L实例&#xff09; 华为云云耀云服务器…...

Linux大老都是怎么记住这么多命令的?

今天给大家带来的是面试/实际工作中经常用到的Linux相关操作命令: 一. vi/vim编辑器 ---->文本编辑器 作用&#xff1a;创建文件&#xff0c;编辑文件&#xff0c;查看文件 格式&#xff1a;vi/vim 文件的名字 解析&#xff1a;如果该文件不存在&#xff0c;vi就会创建该…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

shell脚本质数判断

shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数&#xff09;shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数&#xff09; 思路&#xff1a; 1:1 2:1 2 3:1 2 3 4:1 2 3 4 5:1 2 3 4 5-------> 3:2 4:2 3 5:2 3…...