代码随想录训练营第四十八天|198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

198.打家劫舍 

力扣题目链接(opens new window)

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

  • 示例 1:
  • 输入:[1,2,3,1]
  • 输出:4

解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。   偷窃到的最高金额 = 1 + 3 = 4 。

  • 示例 2:
  • 输入:[2,7,9,3,1]
  • 输出:12 解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。   偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400

思路

当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。

因此,当前状态和前面状态会有一种依赖关系,那么这种依赖关系都是动规的递推公式。

当然以上是大概思路,打家劫舍是dp解决的经典问题,接下来我们来动规五部曲分析如下:

1.确定dp数组(dp table)以及下标的含义

dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]

2.确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。

如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ,即:第i-1房一定是不考虑的,找出 下标i-2(包括i-2)以内的房屋,最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间,那么dp[i] = dp[i - 1],即考 虑i-1房,(注意这里是考虑,并不是一定要偷i-1房

然后dp[i]取最大值,即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3.dp数组如何初始化

从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出,递推公式的基础就是dp[0] 和 dp[1]

从dp[i]的定义上来讲,dp[0] 一定是 nums[0],dp[1]就是nums[0]和nums[1]的最大值即:dp[1] = max(nums[0], nums[1]);

代码如下:

vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

4.确定遍历顺序

dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历!

代码如下:

for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}

5.举例推导dp数组

以示例二,输入[2,7,9,3,1]为例。

198.打家劫舍

红框dp[nums.size() - 1]为结果。

以上分析完毕,C++代码如下:

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];vector<int> dp(nums.size());dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[nums.size() - 1];}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

总结

打家劫舍是DP解决的经典题目也是入门级题目,后面还会变种方式来打劫的。

213.打家劫舍II  

力扣题目链接(opens new window)

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,能够偷窃到的最高金额。

示例 1:

  • 输入:nums = [2,3,2]

  • 输出:3

  • 解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

  • 示例 2:

  • 输入:nums = [1,2,3,1]

  • 输出:4

  • 解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

  • 示例 3:

  • 输入:nums = [0]

  • 输出:0

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

 思路 

这道题目和198.打家劫舍 (opens new window)是差不多的,唯一区别就是成环了。

对于一个数组,成环的话主要有如下三种情况:

  • 情况一:考虑不包含首尾元素

213.打家劫舍II

  • 情况二:考虑包含首元素,不包含尾元素

213.打家劫舍II1

  • 情况三:考虑包含尾元素,不包含首元素

213.打家劫舍II2

注意我这里用的是"考虑",例如情况三,虽然是考虑包含尾元素,但不一定要选尾部元素! 对于情况三,取nums[1] 和 nums[3]就是最大的。

而情况二 和 情况三 都包含了情况一了,所以只考虑情况二和情况三就可以了

分析到这里,本题其实比较简单了。 剩下的和力扣题目链接(opens new window)就是一样的了。

代码如下:

// 注意注释中的情况二情况三,以及把198.打家劫舍的代码抽离出来了
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2); // 情况二int result2 = robRange(nums, 1, nums.size() - 1); // 情况三return max(result1, result2);}// 198.打家劫舍的逻辑int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size());dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[end];}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

总结

成环之后还是难了一些的, 不少题解没有把“考虑房间”和“偷房间”说清楚。

这就导致大家会有这样的困惑:情况三怎么就包含了情况一了呢? 本文图中最后一间房不能偷啊,偷了一定不是最优结果。

所以我在本文重点强调了情况一二三是“考虑”的范围,而具体房间偷与不偷交给递推公式去抉择。

这样就不难理解情况二和情况三包含了情况一了。

337.打家劫舍III

力扣题目链接(opens new window)

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

337.打家劫舍III

思路

这道题目和 198.打家劫舍 (opens new window),213.打家劫舍II (opens new window)也是如出一辙,只不过这个换成了树。

如果对树的遍历不够熟悉的话,那本题就有难度了。

对于树的话,首先就要想到遍历方式,前中后序(深度优先搜索)还是层序遍历(广度优先搜索)。

本题一定是要后序遍历,因为通过递归函数的返回值来做下一步计算

与198.打家劫舍,213.打家劫舍II一样,关键是要讨论当前节点抢还是不抢。

如果抢了当前节点,两个孩子就不能动,如果没抢当前节点,就可以考虑抢左右孩子(注意这里说的是“考虑”

暴力递归

代码如下:

class Solution {
public:int rob(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return root->val;// 偷父节点int val1 = root->val;if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left,相当于不考虑左孩子了if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right,相当于不考虑右孩子了// 不偷父节点int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子return max(val1, val2);}
};
  • 时间复杂度:O(n^2),这个时间复杂度不太标准,也不容易准确化,例如越往下的节点重复计算次数就越多
  • 空间复杂度:O(log n),算上递推系统栈的空间

当然以上代码超时了,这个递归的过程中其实是有重复计算了。

我们计算了root的四个孙子(左右孩子的孩子)为头结点的子树的情况,又计算了root的左右孩子为头结点的子树的情况,计算左右孩子的时候其实又把孙子计算了一遍。

记忆化递推

所以可以使用一个map把计算过的结果保存一下,这样如果计算过孙子了,那么计算孩子的时候可以复用孙子节点的结果。

代码如下:

class Solution {
public:unordered_map<TreeNode* , int> umap; // 记录计算过的结果int rob(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return root->val;if (umap[root]) return umap[root]; // 如果umap里已经有记录则直接返回// 偷父节点int val1 = root->val;if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->leftif (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right// 不偷父节点int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子umap[root] = max(val1, val2); // umap记录一下结果return max(val1, val2);}
};

  • 时间复杂度:O(n)
  • 空间复杂度:O(log n),算上递推系统栈的空间

动态规划

在上面两种方法,其实对一个节点 偷与不偷得到的最大金钱都没有做记录,而是需要实时计算。

而动态规划其实就是使用状态转移容器来记录状态的变化,这里可以使用一个长度为2的数组,记录当前节点偷与不偷所得到的的最大金钱。

这道题目算是树形dp的入门题目,因为是在树上进行状态转移,我们在讲解二叉树的时候说过递归三部曲,那么下面我以递归三部曲为框架,其中融合动规五部曲的内容来进行讲解

  1. 确定递归函数的参数和返回值

这里我们要求一个节点 偷与不偷的两个状态所得到的金钱,那么返回值就是一个长度为2的数组。

参数为当前节点,代码如下:

vector<int> robTree(TreeNode* cur) {

其实这里的返回数组就是dp数组。

所以dp数组(dp table)以及下标的含义:下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱。

所以本题dp数组就是一个长度为2的数组!

那么有同学可能疑惑,长度为2的数组怎么标记树中每个节点的状态呢?

别忘了在递归的过程中,系统栈会保存每一层递归的参数

如果还不理解的话,就接着往下看,看到代码就理解了哈。

 2.确定终止条件

在遍历的过程中,如果遇到空节点的话,很明显,无论偷还是不偷都是0,所以就返回

if (cur == NULL) return vector<int>{0, 0};

这也相当于dp数组的初始化

 3.确定遍历顺序

首先明确的是使用后序遍历。 因为要通过递归函数的返回值来做下一步计算。

通过递归左节点,得到左节点偷与不偷的金钱。

通过递归右节点,得到右节点偷与不偷的金钱。

代码如下:

// 下标0:不偷,下标1:偷
vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右
// 中

 4.确定单层递归的逻辑

如果是偷当前节点,那么左右孩子就不能偷,val1 = cur->val + left[0] + right[0]; (如果对下标含义不理解就再回顾一下dp数组的含义

如果不偷当前节点,那么左右孩子就可以偷,至于到底偷不偷一定是选一个最大的,所以:val2 = max(left[0], left[1]) + max(right[0], right[1]);

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

代码如下:

vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右// 偷cur
int val1 = cur->val + left[0] + right[0];
// 不偷cur
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};

 5.举例推导dp数组

以示例1为例,dp数组状态如下:(注意用后序遍历的方式推导

最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱

递归三部曲与动规五部曲分析完毕,C++代码如下:

class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}// 长度为2的数组,0:不偷,1:偷vector<int> robTree(TreeNode* cur) {if (cur == NULL) return vector<int>{0, 0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);// 偷cur,那么就不能偷左右节点。int val1 = cur->val + left[0] + right[0];// 不偷cur,那么可以偷也可以不偷左右节点,则取较大的情况int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}
};

  • 时间复杂度:O(n),每个节点只遍历了一次
  • 空间复杂度:O(log n),算上递推系统栈的空间

总结

这道题是树形DP的入门题目,通过这道题目大家应该也了解了,所谓树形DP就是在树上进行递归公式的推导。

所以树形DP也没有那么神秘!

只不过平时我们习惯了在一维数组或者二维数组上推导公式,一下子换成了树,就需要对树的遍历方式足够了解!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/134557.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于PyTorch使用LSTM实现新闻文本分类任务

本文参考 PyTorch深度学习项目实战100例 https://weibaohang.blog.csdn.net/article/details/127154284?spm1001.2014.3001.5501 文章目录 本文参考任务介绍做数据的导入 环境介绍导入必要的包介绍torchnet和keras做数据的导入给必要的参数命名加载文本数据数据前处理模型训…

Android高级开发-APK极致优化

九道工序 1. SVG(Scalable Vector Graphics)可缩放矢量图 使用矢量图代替位图可以减小 APK 的尺寸&#xff0c;因为可以针对不同屏幕密度调整同一文件的大小&#xff0c;而不会降低图像质量。 矢量图首次加载时可能消耗更多的 CPU 资源。之后&#xff0c;二者的内存使用率和…

Java集合之LinedList

LinedList类实现了List接口&#xff0c;他提供了&#xff08;双向的&#xff09;链表数据结构 在该链表中的每一个元素除了存储本身的内容之外还存储指向前一个元素的指针和指向后一个元素的指针&#xff0c;下图展示了一个包含三个元素的双向链表&#xff0c;每个链表都有一个…

jeesite实现excel导入功能(保姆级图文教程)

文章目录 前言一、准备工作1.准备一个excel模板,放入static目录2.application.yml文件中设置文件存储路径3.使用easyexcel插件解析excel数据,pom文件导入easyexcel二、使用步骤1.列表页添加下载模板按钮2.表单页添加文件上传3. 创建excel解析对应实体4.后台完成文件上传代码,…

深入探索智能问答:从检索到生成的技术之旅

目录 一、智能问答概述1. **语义理解**2. **知识库和数据库**3. **上下文感知**4. **动态学习和自适应** 二、发展历程1. **基于规则的系统**2. **统计方法的兴起**3. **深度学习和神经网络的突破**4. **预训练模型** 三、智能问答系统的主要类型四、基于知识库的问答系统五、基…

机器视觉之Basler工业相机使用和配置方法(C++)

basler工业相机做双目视觉用&#xff0c;出现很多问题记录一下&#xff1a; 首先是多看手册&#xff1a;https://zh.docs.baslerweb.com/software 手册内有所有的源码和参考示例&#xff0c;实际上在使用过程中&#xff0c;大部分都是这些源码&#xff0c;具体项目选择对应的…

【微信小程序】项目初始化

| var() CSS 函数可以插入一个自定义属性&#xff08;有时也被称为“CSS 变量”&#xff09;的值&#xff0c;用来代替非自定义 属性中值的任何部分。 1.初始化样式与颜色 view,text{box-sizing: border-box; } page{--themColor:#ad905c;--globalColor:#18191b;--focusColor…

【测试开发】答疑篇 · 什么是软件测试

【测试开发】答疑篇 文章目录 【测试开发】答疑篇1. 生活中的测试2. 什么是软件测试3. 为什么要有测试/没有测试行不行4. 软件测试和软件开发的区别5. 软件测试和软件调试之间的区别6. 软件测试的岗位7. 优秀测试人员具备的素质 【测试开发】答疑篇 软件不一定是桌面应用&#…

JSON和全局异常处理

目录 1️⃣JSON 一、什么是json&#xff1f; 二、与javascript的关系 三、语法格式 四、注意事项 五、总结 六&#xff0c;使用json 1导入pom.xml依赖 2.配置spring-mvc.xml 3. ResponseBody注解使用 创建一个web层控制器 编写ClazzBiz 实现接口 测试&#xff1a; …

树莓派4b装系统到运行 Blazor Linux 本地程序全记录

在Linux下运行gui程序,咱也是第一次做,属于是瞎子过河乱摸一通,写得有什么不对和可以优化的地方,希望各位看官斧正斧正. ##1. 下载烧录器 https://www.raspberrypi.com/software/####我选择的是Raspbian 64位系统,并配置好ssh账号密码,wifi,以便启动后可以直接黑屏ssh连接 ##…

成都收录《乡村振兴战略下传统村落文化旅游设计》许少辉八一著作

成都收录《乡村振兴战略下传统村落文化旅游设计》许少辉八一著作已收录至成都

4基于pytorch的蚁群算法求解TSP(旅行商问题),访问一座城市并回到最初位置的最佳路径,解决组合中的NP问题。程序已调通,替换自己的数据可以直接运行。

基于pytorch的蚁群算法求解TSP(旅行商问题)&#xff0c;访问一座城市并回到最初位置的最佳路径&#xff0c;解决组合中的NP问题。程序已调通&#xff0c;替换自己的数据可以直接运行。 4pytorchTSP路径优化 (xiaohongs4pytorchTSP路径优化 (xiaohongshu.com)4pytorchTSP路径优化…

Vim的基础操作

前言 本文将向您介绍关于vim的基础操作 基础操作 在讲配置之前&#xff0c;我们可以新建一个文件 .vimrc&#xff0c;并用vim打开在里面输入set nu 先给界面加上行数&#xff0c;然后shift &#xff1b;输入wq退出 默认打开&#xff1a;命令模式 在命令模式中&#xff1a…

TCP详解之三次握手和四次挥手

TCP详解之三次握手和四次挥手 1. TCP基本认识 1.1 什么是 TCP TCP是面向连接的、可靠的、基于字节流的传输层通信协议。 1.2 TCP协议段格式 我们先来看看TCP首部协议的格式 我们先来介绍一些与本文关联比较大的字段&#xff0c;其他字段不做详细阐述。 序列号&#xff1a…

基于SSM框架的《超市订单管理系统》Web项目开发(第二天)完成登录模块和用户退出模块

《超市订单管理系统》&#xff08;第二天&#xff09; 基于SSM框架的Web项目开发 ​ 昨天我们实现了登录功能&#xff0c;但是用的是模拟数据。今天我们要链接数据库整合SpirngMybatis&#xff0c;读取数据库中的真实数据&#xff0c;用来跟我们输入的userCode和userPassword进…

制作立体图像实用软件:3DMasterKit 10.7 Crack

3DMasterKit 软件专为创建具有逼真 3D 和运动效果的光栅图片而设计&#xff1a;翻转、动画、变形和缩放。 打印机、广告工作室、摄影工作室和摄影师将发现 3DMasterKit 是一种有用且经济高效的解决方案&#xff0c;可将其业务扩展到新的维度&#xff0c;提高生成的 3D 图像和光…

Git - Git Merge VS Git Rebase

文章目录 概述Flow View小结 概述 Git merge和Git rebase是两种不同的版本控制工作流程&#xff0c;它们用于将一个分支的更改合并到另一个分支。它们有不同的工作原理和应用场景&#xff0c;下面是它们的主要区别&#xff1a; 合并的方式&#xff1a; Git Merge&#xff1a;合…

用c++实现五子棋小游戏

五子棋是一款经典小游戏&#xff0c;今天我们就用c实现简单的五子棋小游戏 目录 用到的算法&#xff1a; 思路分析 定义变量 开始写代码 完整代码 结果图&#xff1a; 用到的算法&#xff1a; 合法移动的判断&#xff1a;isValidMove 函数通过检查指定位置是否在棋盘范…

基于matlab实现的 BPSK调制AWGN通道未编码数据误码率程序

完整程序&#xff1a; clear; close all; clc; c0; rate1; %Code rate N10000000; %Number of bits for EbNoc0:1:10 %Ratio of bit energy to no…

Stream流处理快速上手最佳实践 | 京东物流技术团队

一 引言 JAVA1.8得益于Lambda所带来的函数式编程&#xff0c;引入了一个全新的Stream流概念Stream流式思想类似于工厂车间的“生产流水线”&#xff0c;Stream流不是一种数据结构&#xff0c;不保存数据&#xff0c;而是对数据进行加工处理。Stream可以看作是流水线上的一个工…