当前位置: 首页 > 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就会创建该…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

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

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

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

《Offer来了:Java面试核心知识点精讲》大纲

文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...