打家劫舍系列(三合一)(动态规划)

本篇博客讲解一下动态规划的打家劫舍系列,对应的力扣题目分别是198. 打家劫舍,213. 打家劫舍 II,337. 打家劫舍 III

198. 打家劫舍:

题目:

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

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

示例 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 。

提示:

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

思路:

如果刚接触这样的题目,会有点困惑,当前的状态我是偷还是不偷呢?

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

所以这里就更感觉到,当前状态和前面状态会有一种依赖关系,那么这种依赖关系都是动规的递推公式。

打家劫舍是dp解决的经典问题,接下来我们来动规五部曲分析如下:

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

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

  1. 确定递推公式

决定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]);

  1. 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]);

代码如下:

        dp = [0] * len(nums) 
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
  1. 确定遍历顺序

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

代码如下:

        for i in range(2, len(nums)):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
  1. 举例推导dp数组

以示例二,输入[2,7,9,3,1]为例。
在这里插入图片描述
红框dp[len(nums) - 1]为结果。

代码及详细注释:

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [0] * len(nums)  # 创建一个长度为nums的列表dp,用于存储偷取到当前房屋时的最大价值
        if len(nums) < 2:  # 如果房屋数量小于2,直接返回第一个房屋的价值
            return nums[0]
        dp[0] = nums[0]  # 第一个房屋的最大价值就是第一个房屋的价值
        dp[1] = max(nums[0], nums[1])  # 第二个房屋的最大价值为第一个和第二个房屋价值的较大值
        for i in range(2, len(nums)):  # 从第三个房屋开始遍历
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])  # 当前房屋的最大价值为偷取当前房屋与不偷取当前房屋的较大值
        return dp[len(nums) - 1]  # 返回最后一个房屋的最大价值

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

213. 打家劫舍 II:

题目:

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

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

示例 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 = [1,2,3]

输出:

3

提示:

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

思路:

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

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

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

在这里插入图片描述

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

在这里插入图片描述

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

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

而情况二 和 情况三 都包含了情况一了,所以只考虑情况二和情况三就可以了。
剩下的和198.打家劫舍就是一样的了。

代码及详细注释:

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:  # 如果只有一个房屋,直接返回该房屋的价值
            return nums[0]
        result1 = self.rob_range(nums, 0, len(nums) - 1)  # 假设偷取第一间到倒数第二间房屋的最大价值
        result2 = self.rob_range(nums, 1, len(nums))  # 假设偷取第二间到最后一间房屋的最大价值
        return max(result1, result2)  # 返回两种情况下的最大价值

    def rob_range(self, nums, start, end):
        dp = [0] * len(nums)  # 创建一个长度为nums的列表dp,用于存储偷取到当前房屋时的最大价值
        if (end - start) < 2:  # 如果房屋数量小于2,直接返回房屋的价值
            return nums[start]
        dp[start] = nums[start]  # 第一间房屋的最大价值就是第一间房屋的价值
        dp[start + 1] = max(nums[start], nums[start + 1])  # 第二间房屋的最大价值为第一和第二间房屋价值的较大值
        for i in range(start + 2, end):  # 从第三间房屋开始遍历
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])  # 当前房屋的最大价值为偷取当前房屋与不偷取当前房屋的较大值
        return dp[end - 1]  # 返回最后一间房屋的最大价值

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

337. 打家劫舍 III:

题目:

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。

除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。

示例 1:

在这里插入图片描述

输入:

root = [3,2,3,null,3,null,1]

输出:

7

解释:

小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

在这里插入图片描述

输入:

root = [3,4,5,1,3,null,1]

输出:

9

解释:

小偷一晚能够盗取的最高金额 4 + 5 = 9

提示:

  • 树的节点数在 [1, 104] 范围内
  • 0 <= Node.val <= 104

思路:

这道题目和 198.打家劫舍,213.打家劫舍II也是如出一辙,只不过这个换成了

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

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

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

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

这里可以使用一个长度为2的数组,记录当前节点偷与不偷所得到的的最大金钱。
下面以递归三部曲为框架,其中融合动规五部曲的内容来进行讲解。

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

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

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

def rob(self, root: Optional[TreeNode]) -> int:
    dp = self.traversal(root)
def traversal(self, cur):
    ...........
    return (value0, value1)

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

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

  1. 确定终止条件

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

        if cur == NULL:
            return (0, 0)

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

  1. 确定遍历顺序

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

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

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

代码如下:

        left = self.traversal(cur.left) 
        right = self.traversal(cur.right)
  1. 确定单层递归的逻辑

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

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

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

代码如下:

        left = self.traversal(cur.left)  # 递归调用traversal方法计算左子树的最大价值
        right = self.traversal(cur.right)  # 递归调用traversal方法计算右子树的最大价值
       
        value0 = max(left[0], left[1]) + max(right[0], right[1])  # 不偷取当前节点的最大价值为左子树和右子树的最大价值之和
        value1 = cur.val + left[0] + right[0]  # 偷取当前节点的最大价值为当前节点的价值加上左子树和右子树不偷取当前节点的最大价值之和
        return (value0, value1)  # 返回偷取当前节点和不偷取当前节点的最大价值
  1. 举例推导dp数组
    以示例1为例,dp数组状态如下:(注意用后序遍历的方式推导)

在这里插入图片描述
最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱。

代码及详细注释:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        dp = self.traversal(root)  # 调用traversal方法获取偷取当前节点和不偷取当前节点的最大价值
        return max(dp)  # 返回偷取当前节点和不偷取当前节点的最大价值中的较大值

    def traversal(self, cur):
        if not cur:  # 如果当前节点为空,返回(0, 0),表示偷取当前节点和不偷取当前节点的最大价值都为0
            return (0, 0)

        left = self.traversal(cur.left)  # 递归调用traversal方法计算左子树的最大价值
        right = self.traversal(cur.right)  # 递归调用traversal方法计算右子树的最大价值

        value0 = max(left[0], left[1]) + max(right[0], right[1])  # 不偷取当前节点的最大价值为左子树和右子树的最大价值之和
        value1 = cur.val + left[0] + right[0]  # 偷取当前节点的最大价值为当前节点的价值加上左子树和右子树不偷取当前节点的最大价值之和
        return (value0, value1)  # 返回偷取当前节点和不偷取当前节点的最大价值

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

总结:

打家劫舍系列跟背包问题比起来还是比较简单和好理解的

劫舍系列简单来说就是 数组上连续元素二选一,成环之后连续元素二选一,在树上连续元素二选一,所能得到的最大价值。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

关于C#中的HashSet<T>与List<T>

HashSet<T> 表示值的集合。这个集合的元素是无须列表&#xff0c;同时元素不能重复。由于这个集合基于散列值&#xff0c;不能通过数组下标访问。 List<T> 表示可通过索引访问的对象的强类型列表。内部是用数组保存数据&#xff0c;不是链表。元素可重复&#xf…

【数据结构】快速排序,归并排序

快速排序 1.hoare版本 根据动图的演示&#xff0c;整理的思路如下&#xff0c; 1.定义left,right,key。key默认是左边第一个元素&#xff0c;像两个指针&#xff0c;左边找比key大的&#xff0c;右边找比k小的&#xff0c;找到的话&#xff0c;交换二者&#xff0c;往返这个过…

《移动通信原理与应用》——QAM调制解调仿真

目录 一、QAM调制与解调仿真流程图&#xff1a; 二、仿真结果&#xff1a; 三、Matlab仿真程序代码如下&#xff1a; 一、QAM调制与解调仿真流程图&#xff1a; QAM调制仿真流程图&#xff1a; QAM解调仿真流程图&#xff1a; 二、仿真结果&#xff1a; &#xff08;1&…

JOSEF约瑟 中间继电器JZ14-44Z/4 不带外罩和接线座

系列型号 JZ14-014Z/0中间继电器;JZ14-014Z/1中间继电器; JZ14-014Z/2中间继电器;JZ14-014Z/4中间继电器; JZ14-014J/0中间继电器;JZ14-014J/1中间继电器; JZ14-014J/2中间继电器;JZ14-014J/3中间继电器; JZ14-014J/4中间继电器;JZ14-140Z/0中间继电器; JZ14-140Z/1中间继…

Web06--JavaScript基础02

1、JS流程控制语句 JS与Java一样&#xff0c;也有三个流程控制语句&#xff1a; 顺序结构 选择结构 循环结构 1.1 选择结构 1.1.1 if结构 <script type"text/javascript">if (条件表达式) {代码块;} else if(条件表达式){代码块;} else {代码块;} </scr…

Flink中的容错机制

一.容错机制 在Flink中&#xff0c;有一套完整的容错机制来保证故障后的恢复&#xff0c;其中最重要的就是检查点。 1.1 检查点&#xff08;Checkpoint&#xff09; 在流处理中&#xff0c;我们可以用存档读档的思路&#xff0c;将之前某个时间点的所有状态保存下来&#xf…

MATLAB实现岭回归数学建模算法

岭回归&#xff08;Ridge Regression&#xff09;是一种线性回归的扩展&#xff0c;用于处理多重共线性&#xff08;multicollinearity&#xff09;的问题。多重共线性是指自变量之间存在高度相关性的情况&#xff0c;这可能导致线性回归模型的不稳定性和过拟合。 岭回归通过在…

风二西CTF流量题大集合-刷题笔记|基础题(4)

61.sql2 sql.pcapng flag{a3eb0ff8-e467-5036-7c9b-287f6848d5f3} 62.冰蝎2.0 swt1.pcapng flag{0867c25f69f0c62c970408ccefe29bb7} 64.gs哥斯拉流量4.0 gs.pcapng flag{0fffbfa87e5508955b397950502db0bd} 65.冰蝎web流量 webshell.pcapng flag{da2c30d9318a0d80b4bfa…

C++——IOStream

什么是IO&#xff1f; C语言和C&#xff0c;我们其实已经接触到了两个IO的概念 #include<stdio.h> #include<iostream> iostream&#xff0c;便是IO流&#xff0c;其中I表示in&#xff0c;O表示out&#xff0c;代表着用户的输入和终端的输出。在之前的C语法中&a…

【服务器】安装Docker环境

目录 &#x1f33a;【前言】 &#x1f33c;1. 打开Xshell软件 &#x1f33b;2. 安装Docker环境 ①&#xff1a;下载docker.sh脚本 ②&#xff1a;列出下载的内容 ③&#xff1a;执行一下get-docker.sh文件&#xff0c;安装docker ④&#xff1a;运行docker服务 ⑤&…

内网安全管理系统(保密管理系统)

在当今信息化的时代&#xff0c;企业的内网已经成为其核心资产的重要组成部分。 随着企业的快速发展和信息化程度的提升&#xff0c;内网安全问题日益凸显&#xff0c;如何保障内网的安全和机密信息的保密性&#xff0c;已经成为企业亟待解决的问题。 内网安全管理系统(保密管…

定时任务组件Quartz

Quartz介绍 Quartz 是一个功能丰富的开源作业调度库&#xff0c;几乎可以集成到任何 Java 应用程序中 - 从最小的独立应用程序到最大的电子商务系统。Quartz 可用于创建简单或复杂的计划&#xff0c;以执行数十、数百甚至数万个作业;其任务被定义为标准 Java 组件的作业&#x…

了解HTTP/1.1、HTTP/1.0 和 HTTP/2.0

HTTP/1.1、HTTP/1.0 和 HTTP/2.0 是超文本传输协议&#xff08;HTTP&#xff09;的三个主要版本 先解释一下什么是超文本协议 超文本传输协议&#xff08;HyperText Transfer Protocol&#xff0c;简称 HTTP&#xff09;是互联网上应用最广泛的一种网络协议。设计 HTTP 的初衷是…

STM32(--001) Win10、Win11 上的驱动安装说明

一、USB线插到 CMSIS-DAP 接口上&#xff0c;将自动识别到两个设备 ① CMSIS-DAP&#xff1a;用于烧录代码、在线硬件仿真; 在Keil里烧录&#xff0c;无需通过FlyMCU; ② USB转TTL&#xff1a;用于开发板与电脑间串口通信 &#xff0c;即USART1, TX-PA9、RX-PA10; 接口备注&a…

Vue前端环境搭建以及项目搭建

安装node.js 安装node.js主要是为了安装npm工具&#xff0c;用于管理js包等&#xff0c;类似于java的maven。 去官网下载安装。 配置新的镜像源 npm config set registry https://registry.npmmirror.com安装webpack webpack是前端项目打包工具。 命令&#xff1a; npm…

2023年春秋杯网络安全联赛冬季赛 Writeup

文章目录 Webezezez_phppicup Misc谁偷吃了外卖modules明文混淆 Pwnnmanagerbook Reupx2023 CryptoCF is Crypto Faker 挑战题勒索流量Ezdede 可信计算 Web ezezez_php 反序列化打redis主从复制RCE&#xff1a;https://www.cnblogs.com/xiaozi/p/13089906.html <?php c…

【办公类-22-01】20240123 UIBOT逐一提取CSDN质量分

背景需求&#xff1a; 最近每天传2份Python&#xff0c;发现平均分从73.5降到了72.7。网上搜索一下原因&#xff0c;发现每篇CSDN都有一个评分&#xff08;以下是查分网站&#xff09; https://www.csdn.net/qchttps://www.csdn.net/qc 但是一篇一篇查询&#xff0c;显然太繁…

【图论--搜索篇】宽度优先搜索,广度优先搜索

今日语录&#xff1a;成功是一种心态&#xff0c;如果你相信自己能做到&#xff0c;那你已经迈出成功的第一步。 文章目录 宽度优先搜索&#xff08;bfs&#xff09;广度优先搜索&#xff08;dfs&#xff09; 宽度优先搜索&#xff08;bfs&#xff09; #include <iostream&…

(M)unity2D敌人的创建、人物属性设置,遇敌掉血

敌人的创建 1.敌人添加与组件设置 1&#xff09;添加敌人后&#xff0c;刚体添加&#xff0c;碰撞体添加&#xff08;一个碰撞体使猪在地上走&#xff0c;不接触人&#xff0c;另一个碰撞体组件使人和猪碰在一起产生伤害&#xff09; ①刚体 ②碰撞体一 设置的只在脚下&a…

图书管理系统-Python

相关代码&#xff1a; # Time: 2024/1/23 16:16 # Author: 马龙强 # File: 图书管理系统.py # software: PyCharm class Book():def __init__(self,name,auther,status,bookindex):self.name nameself.auther autherself.status statusself.bookindex bookindexdef __str…