力扣刷题记录（七）动态规划（三）打家劫舍

曾经终败给现在 2022-10-06 15:56 162阅读 0赞

① 题号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 。  
提示：  
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 dp(nums.size());  
dp\[0\] = nums\[0\];  
dp\[1\] = max(nums\[0\], nums\[1\]);  
4.确定遍历顺序  
dp\[i\] 是根据dp\[i - 2\] 和 dp\[i - 1\] 推导出来的，那么一定是从前到后遍历！  
![在这里插入图片描述][20210614221059118.png]  
5.举例推导dp数组  
以示例二，输入\[2,7,9,3,1\]为例。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70]  
答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20210614222322392.png]  
② 题号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 = \[0\] 输出：0 提示：  
1 <= nums.length <= 100  
0 <= nums\[i\] <= 1000

解析：

这道题目和198.打家劫舍是差不多的，唯一区别就是成环了。  
对于一个数组，成环的话主要有如下三种情况：  
情况一：考虑不包含首尾元素  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 2]  
情况二：考虑包含首元素，不包含尾元素  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 3]  
情况三：考虑包含尾元素，不包含首元素  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 4]  
**注意我这里用的是"考虑"，例如情况三，虽然是考虑包含尾元素，但不一定要选尾部元素！ 对于情况三，取nums\[1\] 和 nums\[3\]就是最大的。  
而情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了**。  
分析到这里，本题其实比较简单了。 剩下的和198.打家劫舍就是一样的了。

答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][20210614224453430.png]  
③ 题号337.打家劫舍 III  
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。  
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 7]  
解析：  
这道题目和 198.打家劫舍，213.打家劫舍II也是如出一辙，只不过这个换成了树。  
如果对树的遍历不够熟悉的话，那本题就有难度了。  
对于树的话，首先就要想到遍历方式，前中后序（深度优先搜索）还是层序遍历（广度优先搜索）。  
本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。  
与198.打家劫舍，213.打家劫舍II一样，关键是要讨论当前节点抢还是不抢。  
如果抢了当前节点，两个孩子就不是动，如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）。

答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 8]

[20210614221059118.png]: /images/20221005/4d8281d32b1d440e8ca26d313fb2f14a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70]: /images/20221005/33674b0eb0314e5bb646c938c7eca520.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1]: /images/20221005/ff2c07aef2f84dee923dfa30a85cd398.png
[20210614222322392.png]: /images/20221005/b5deb84898074fa1a8dafb430b2f0c4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 2]: /images/20221005/3efe909924194f0d8ab9f4624e7a31ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 3]: /images/20221005/a19abdbe3ec34a518bda417638aff3b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 4]: /images/20221005/df62c8b3ca04471bb8933096a462d4db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 5]: /images/20221005/275201f8d1784324a22b1fd8fcc14604.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 6]: /images/20221005/5b29c82ca2c7494ebb2cb27798c02278.png
[20210614224453430.png]: /images/20221005/55aa4b952b1a47b8b268a2b00691a9e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 7]: /images/20221005/bca5ace3ddf8475d8560310530c8d790.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 8]: /images/20221005/b38db2426c704046a5671aa5944cfa3e.png