一篇文章带你用动态规划解决打家劫舍问题
动态规划的解题步骤可以分为以下五步,大家先好好记住
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;}
总的来说只要结合了核心思想“偷这个就不能偷那个” 打家劫舍问题还是很简单的
相关文章:
一篇文章带你用动态规划解决打家劫舍问题
动态规划的解题步骤可以分为以下五步,大家先好好记住 1.创建dp数组以及明确dp数组下标的含义 2.制定递推公式 3.初始化 4.遍历顺序 5.验证结果 根据打家劫舍的题意:两个直接相连的房子在同一天晚上被打劫会触发警报 所以我们制定出核心策略——偷东…...
idea中导入eclipse的javaweb项目——tomact服务(保姆级别)
idea中导入eclipse的javaweb项目——tomact服务(保姆级别) 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
作者:小傅哥 - 百度搜 小傅哥bugstack 博客:bugstack.cn 沉淀、分享、成长,让自己和他人都能有所收获!😄 大家好,我是技术UP主小傅哥。 清华大学计算机系的超大规模训练模型 ChatGLM-130B 使用效果非常牛&…...
基于Pytest+Allure+Excel的接口自动化测试框架
1. Allure 简介 简介 Allure 框架是一个灵活的、轻量级的、支持多语言的测试报告工具,它不仅以 Web 的方式展示了简介的测试结果,而且允许参与开发过程的每个人可以从日常执行的测试中,最大限度地提取有用信息。 Allure 是由 Java 语言开发的…...
20.2 FMC驱动SDRAM的时序初始化实现及内存测试
继续上一篇的话题,写到SDRAM通过CubeMx配置后,在工程代码编写时直接引用的是我事先写好的时序初始化、内存测试文件,而未对其进行详细的解释,所以本篇文章就来娓娓道来。不多说,开始吧 SDRAM的初始化流程简述 SDRAM初…...
联想电脑一键重装系统Win10操作方法
很多用户都会利用重装系统的方法,来解决系统崩溃、病毒感染等问题。但是,很多新手用户不知道联想电脑Win10系统重装的详细方法步骤,下面小编给大家详细介绍关于联想电脑Win10系统重装的操作方法,帮助大家轻松快速地完成系统的重装…...
Mysql数据库 1.概述
Mysql内容概述 1. Mysql概述 数据库相关概念: 名称 全称 简称 数据库 存储数据的仓库,数据是有组织的进行存储 …...
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 容器中数据的方式 端口映射 容器互联(使用centos镜像) 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个级别: 项目-大多数静态配置发生在pom.xml中安装-这是为Maven安装添加的…...
第十八章 类和对象——多态
一、多态的基本概念 多态是C面向对象三大特性之一 多态分为两类 静态多态: 函数重载 和 运算符重载属于静态多态,复用函数名 动态多态: 派生类和虚函数实现运行时多态 静态多态和动态多态区别: 静态多态的函数地址早绑定 - 编译阶段确定函数地址 动…...
京东数据平台:2023年服饰行业销售数据分析
最近看到有些消费机构分析,不少知名的运动品牌都把“主战场”放到了冲锋衣,那么羽绒服市场就比较危险了。但其实羽绒服市场也有机会点可寻。 先来说冲锋衣。的确,从今年的销售数据以及增长情况,冲锋衣的确会是今年冬天的大热门品…...
Nginx proxy_set_header参数设置
一、不设置 proxy_set_header Host 不设置 proxy_set_header Host 时,浏览器直接访问 nginx,获取到的 Host 是 proxy_pass 后面的值,即 $proxy_host 的值,参考Module ngx_http_proxy_module 1 2 3 4 5 6 7 8 # cat ngx_header.c…...
如何用 ChatGPT 的 Advanced Data Analysis 帮你采集数据?
(注:本文为小报童精选文章,已订阅小报童或加入知识星球「玉树芝兰」用户请勿重复付费) 想采集网页数据却不会写 Python 爬虫?不会就不会吧,ChatGPT 会就可以了 😂 问题描述 朋友最近遇到了一点儿…...
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文件,把第一行的127.0.0.1改成自…...
求最大bit数(java)
题目描述 求一个int类型数字对应的二进制数字中1的最大连续数 例如3的二进制为00000011,最大连续2个1 数据范围:数据组数:11t15,11n1500000进阶: 时间复杂度: O(logn),空间复杂度: O(1) 输入: 200 输出 2 说明 200的二进制表示是11001000&am…...
【Java 进阶篇】JavaScript 与 HTML 的结合方式
JavaScript是一种广泛应用于Web开发中的脚本语言,它与HTML(Hypertext Markup Language)结合使用,使开发人员能够创建交互式和动态的网页。在这篇博客中,我们将深入探讨JavaScript与HTML的结合方式,包括如何…...
华为云云耀云服务器L实例评测 | 实例评测使用之硬件参数评测:华为云云耀云服务器下的 Linux 磁盘目录分析神器 ncdu
华为云云耀云服务器L实例评测 | 实例评测使用之硬件参数评测:华为云云耀云服务器下的 Linux 磁盘目录分析神器 ncdu 介绍华为云云耀云服务器 华为云云耀云服务器 (目前已经全新升级为 华为云云耀云服务器L实例) 华为云云耀云服务器…...
Linux大老都是怎么记住这么多命令的?
今天给大家带来的是面试/实际工作中经常用到的Linux相关操作命令: 一. vi/vim编辑器 ---->文本编辑器 作用:创建文件,编辑文件,查看文件 格式:vi/vim 文件的名字 解析:如果该文件不存在,vi就会创建该…...
LoRa技术未来发展前景:物联网和边缘计算的引领者
随着物联网和边缘计算的快速发展,低功耗广域网(LoRa)技术在连接远距离设备、实现长距离通信和满足低功耗需求方面崭露头角。本文将分析LoRa技术在未来的发展前景,尤其是在物联网和边缘计算领域的潜在影响。 LoRa技术的核心优势 1…...
出现 PowerShell终端执行conda activate无效 解决方法
目录 1. 问题所示2. 原理分析3. 解决方法1. 问题所示 在cmd命令行中执行conda activate 可以成功,但是回pycharm的PowerShell终端执行该命令,一直无效 具体过程如下: PS E:\pythonProject\SteganoGAN-master> conda activate py37 PS E:\pythonProject\SteganoGAN-mas…...
Python实现某音短视频JS XB逆向解析
哈喽兄弟们,今天来实现一下某音短视频的JS逆向解析。 知识点 动态数据抓包在这里插入代码片 requests发送请求 X-Bogus 参数逆向环境模块 python 3.8 运行代码 pycharm 2022.3 辅助敲代码 requests pip install request…...
SecureCRT 自动测试脚本的使用方法
脚本示例(get_batteryifo_interval_2s.vbs): Sub Main Do While(1)crt.Screen.Send "pm_client batteryinfo" & chr(13)crt.Sleep 2000 Loop End Sub 1. 解压 SecureCRT 压缩包(网上下载);…...
常用图像标注工具
1. LabelImg 1)LabelImg 是一款开源的图像标注工具,标签可用于分类和目标检测,它是用 Python 编写的,并使用Qt作为其图形界面,简单好用。注释以 PASCAL VOC 格式保存为 XML 文件,这是 ImageNet 使用的格式。…...
hadoop namenode -format报错显示:命令未找到
这个bug很搞笑,我做分布式搭建时,slaver1和slaver2都可以hadoop name -format,就是master不可以,配置都是一样的,这个第一时间也是想到了环境配置问题 打开环境配置文件编辑 sudo vim ~/.bashrc 添加以下代码&#…...
prostate数据集下载
1. prostatex 下载地址:https://wiki.cancerimagingarchive.net/pages/viewpage.action?pageId23691656 比赛:https://prostatex.grand-challenge.org/ 这个下载的是一个tcia文件,参考这篇文章打开该文件 2. promise12 地址:…...
比较和同步数据库架构和数据:MssqlMerge Pro Crack
比较和同步数据库架构和数据 适用于Oracle、MySQL 和 MariaDB、SQL Server、PostgreSQL、SQLite、MS Access和跨 DBMS 场景 业界领先的文本比较工具中常用的两面板 UI 快速过滤器显示所有/新/更改/新更改 合并两个方向的更改 轻量级:跨 DBMS 工具小于 20 MB…...
R语言——赋值(= ,<- ,<<-)
R语言 R语言——赋值( ,<- ,<<-) 文章目录 R语言一、 与 <- 的区别二、 <<- ,向上一环境层写入变量 R语言中" <- " 与 " " 都可以用来赋值,但R中建议使用" <- “…...
图形界面四则运算计算器(Python+PyQt5)
(1) 导入所需的库和模块。 (2) 创建一个名为Calculator的类,继承自QMainWindow。 (3) 在Calculator类的__init__方法中,调用initUI方法初始化界面。 (4) 在initUI方法中,设置窗口标题和大小,创建显示结果的文本框,并调…...
SQL Server 创建表
切换数据库,判断是否存在 --切换数据库 use DBTEST--判断表是否存在 --创建的所有表都可以在sys.boject中找到,所以这里在sys.objects中查找是否有名字为department的表并且type为U 即用户生成的表 if exists(select * from sys.objects where namedepa…...
JS数组或数组对象去重常用方法
数组去重有许多种方法,下面列举几种常见方法 数组去重数组对象去重 数组去重 使用 Set:将数组转化为 Set 对象,去重后再转化回数组,Set 会自动去重 const arr [1, 2, 3, 2, 1, 4] const newArr [...new Set(arr)] console.log…...
allure测试报告生成逻辑--解决在Jenkins里打开allure报告页面后空白显示无数据问题(以window环境为例)
前言 相信大家在用Jenkins持续集成+ant自动构建+jmeter接口测试+pytest代码.xml文件转化+allure测试报告为一体的接口自动化测试构建过程中,都会遇到Jenkins里打开allure报告页面后空白显示无数据问题这一现象级问题,今天Darren洋就给大家分享一下如何讲讲allure测试报告生成…...
基于JAYA优化的BP神经网络(分类应用) - 附代码
基于JAYA优化的BP神经网络(分类应用) - 附代码 文章目录 基于JAYA优化的BP神经网络(分类应用) - 附代码1.鸢尾花iris数据介绍2.数据集整理3.JAYA优化BP神经网络3.1 BP神经网络参数设置3.2 JAYA算法应用 4.测试结果:5.M…...
JavaScript进阶(二十六):ES各版本特性详解
文章目录 一、ECMAScript简介二、ES6 (ES2015)三、ES7 (ES2016)四、ES8 (ES2017)五、ES9 (ES2018)六、ES10 (ES2019)七、ES11 (ES2020)八、ES12 (ES2021)九、拓展阅读 一、ECMAScript简介 ECMAScript是一种由Ecma国际(前身为欧洲计算机制造商协会,Europ…...
排序算法-快速排序法(QuickSort)
排序算法-快速排序法(QuickSort) 1、说明 快速排序法是由C.A.R.Hoare提出来的。快速排序法又称分割交换排序法,是目前公认的最佳排序法,也是使用分而治之(Divide and Conquer)的方式,会先在数…...
Python 简介
一、Python 简介 Python 是著名的“龟叔” Guido van Rossum 在 1989 年圣诞节期间,为了打发无聊的圣诞节而编写的一个编程语言。牛人就是牛人,为了打发无聊时间竟然写了一个这么牛皮的编程语言。 现在,全世界差不多有 600 多种编程语言&am…...
grafana api创建dashboard 记录
文章目录 json model导入申请api key创建dashboard删除dashboard json model导入 直接在ui通过json model 导入,开发自己用还好,但对非开发人员不太友好,故考虑通过api后台自动创建 api doc : https://grafana.com/docs/grafana/v9.3/devel…...
局域网上IP多播与IP单播关于MAC地址的区别
IP单播进行到局域网上的时候: 网际层使用IP地址进行寻址,各路由器收到IP数据报后,根据其首部中的目的IP地址的网络号部分,基于路由表进行查表转发。 查表转发的结果可指明IP数据报的下一跳路由器的IP地址,但无法指明…...
三数之和[中等]
优质博文:IT-BLOG-CN 一、题目 给你一个整数数组nums,判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! k,同时还满足nums[i] nums[j] nums[k] 0。请你返回所有和为0且不重复的三元组。 注意:答案中不可以…...
基于天牛须优化的BP神经网络(分类应用) - 附代码
基于天牛须优化的BP神经网络(分类应用) - 附代码 文章目录 基于天牛须优化的BP神经网络(分类应用) - 附代码1.鸢尾花iris数据介绍2.数据集整理3.天牛须优化BP神经网络3.1 BP神经网络参数设置3.2 天牛须算法应用 4.测试结果&#x…...
渗透波菜网站
免责声明 本文发布的工具和脚本,仅用作测试和学习研究,禁止用于商业用途,不能保证其合法性,准确性,完整性和有效性,请根据情况自行判断。如果任何单位或个人认为该项目的脚本可能涉嫌侵犯其权利,…...
Spring Boot:Dao层-实例介绍
目录 Dao层的作用Dao层的特点与 Service 层和 Controller 层的关系实例介绍MenuDaoOperatorLogDaoRoleDaoUserDao四个文件的共同点引用的包使用Repository注解继承JpaRepository接口接口的实体类的主键类型使用 Query()注解 Dao层的作用 负责与数据库进行交互,主要…...
接口测试入门:深入理解接口测试!
很多人会谈论接口测试。到底什么是接口测试?如何进行接口测试?这篇文章会帮到你。 一、前端和后端 在谈论接口测试之前,让我们先明确前端和后端这两个概念。 前端是我们在网页或移动应用程序中看到的页面,它由 HTML 和 CSS 编写…...
Redis微服务架构
Redis微服务架构 缓存设计 缓存穿透 缓存穿透是指查询一个根本不存在的数据,缓存层和存储层都不会命中,通常出于容错的考虑,如果从存储层查不到数据则不写入缓层。 缓存穿透将导致不存在的数据每次请求都要到存储层去查询,失去…...
【C++】 局部对象,引用返回
1、new 关键字 会在堆内申请空间,如果仅仅是普通调用构造函数,不会在堆内开辟空间。 2、函数调用会形成栈帧,进行压栈操作,函数调用结束,会进行弹栈。 函数内的局部对象,会随着弹栈,而被销毁(…...
线性代数中涉及到的matlab命令-第二章:矩阵及其运算
目录 1,矩阵定义 2,矩阵的运算 3,方阵的行列式和伴随矩阵 4,矩阵的逆 5,克莱默法则 6,矩阵分块 1,矩阵定义 矩阵与行列式的区别: (1)形式上行列式…...
计算机毕业设计选什么题目好?springboot 美食推荐系统
✍✍计算机编程指导师 ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java实战 |…...
爆肝整理,Jmeter接口性能测试-跨线程调用变量实操(超详细)
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 1、Jmeter中线程运…...
Maven导入程序包jakarta.servlet,但显示不存在
使用前提:(Tomcat10版本)已知tomcat10版本之后,使用jakart.servlet。而tomcat9以及之前使用javax.servlet。 问题描述:在maven仓库有导入了Jakarta程序包,但是界面仍然显示是javax。(下图&…...