前言

代码随想录算法训练营day48

一、Leetcode 198.打家劫舍

1.题目

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

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

示例 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. 1 <= nums.length <= 100
2. 0 <= nums[i] <= 400

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/house-robber

2.解题思路

方法一：动态规划

首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k (k>2)k (k>2) 间房屋，有两个选项：

1. 偷窃第 kk 间房屋，那么就不能偷窃第 k−1k−1 间房屋，偷窃总金额为前 k−2k−2 间房屋的最高总金额与第 kk 间房屋的金额之和。
2. 
3. 不偷窃第 kk 间房屋，偷窃总金额为前 k−1k−1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 kk 间房屋能偷窃到的最高总金额。

用 dp[i]dp[i] 表示前 ii 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

dp[i]=max⁡(dp[i−2]+nums[i],dp[i−1])dp[i]=max(dp[i−2]+nums[i],dp[i−1])

边界条件为：

{dp[0]=nums[0]只有一间房屋，则偷窃该房屋dp[1]=max⁡(nums[0],nums[1])只有两间房屋，选择其中金额较高的房屋进行偷窃{dp[0]=nums[0]dp[1]=max(nums[0],nums[1])只有一间房屋，则偷窃该房屋只有两间房屋，选择其中金额较高的房屋进行偷窃

最终的答案即为 dp[n−1]dp[n−1]，其中 nn 是数组的长度。

class Solution { public int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int length = nums.length; if (length == 1) { return nums[0]; } int[] dp = new int[length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); } return dp[length - 1]; } }

上述方法使用了数组存储结果。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。

class Solution {

3.代码实现

```java class Solution { public int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int length = nums.length; if (length == 1) { return nums[0]; } int first = nums[0], second = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { int temp = second; second = Math.max(first + nums[i], second); first = temp; } return second; } }
```

二、Leetcode 213.打家劫舍II

1.题目

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

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

示例 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. 1 <= nums.length <= 100
2. 0 <= nums[i] <= 1000

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/house-robber-ii

2.解题思路

方法一：动态规划

首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

注意到当房屋数量不超过两间时，最多只能偷窃一间房屋，因此不需要考虑首尾相连的问题。如果房屋数量大于两间，就必须考虑首尾相连的问题，第一间房屋和最后一间房屋不能同时偷窃。

如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。

假设数组 numsnums 的长度为 nn。如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 [0,n−2][0,n−2]；如果不偷窃第一间房屋，则偷窃房屋的下标范围是 [1,n−1][1,n−1]。在确定偷窃房屋的下标范围之后，即可用第 198 题的方法解决。对于两段下标范围分别计算可以偷窃到的最高总金额，其中的最大值即为在 nn 间房屋中可以偷窃到的最高总金额。

假设偷窃房屋的下标范围是 [start,end][start,end]，用 dp[i]dp[i] 表示在下标范围 [start,i][start,i] 内可以偷窃到的最高总金额，那么就有如下的状态转移方程：

dp[i]=max⁡(dp[i−2]+nums[i],dp[i−1])dp[i]=max(dp[i−2]+nums[i],dp[i−1])

边界条件为：

{dp[start]=nums[start]只有一间房屋，则偷窃该房屋dp[start+1]=max⁡(nums[start],nums[start+1])只有两间房屋，偷窃其中金额较高的房屋{dp[start]=nums[start]dp[start+1]=max(nums[start],nums[start+1])只有一间房屋，则偷窃该房屋只有两间房屋，偷窃其中金额较高的房屋

计算得到 dp[end]dp[end] 即为下标范围 [start,end][start,end] 内可以偷窃到的最高总金额。

分别取 (start,end)=(0,n−2)(start,end)=(0,n−2) 和 (start,end)=(1,n−1)(start,end)=(1,n−1) 进行计算，取两个 dp[end]dp[end] 中的最大值，即可得到最终结果。

根据上述思路，可以得到时间复杂度 O(n)O(n) 和空间复杂度 O(n)O(n) 的实现。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额，将空间复杂度降到 O(1)O(1)。

3.代码实现

```java class Solution { public int rob(int[] nums) { int length = nums.length; if (length == 1) { return nums[0]; } else if (length == 2) { return Math.max(nums[0], nums[1]); } return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1)); }

1. public int robRange(int[] nums, int start, int end) {
2.     int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
3. for (int i = start + 2; i <= end; i++) {
4.         int temp = second;
5.         second = Math.max(first + nums[i], second);
6. first = temp;
7.     }
8. return second;
9. }

}

```

三、Leetcode 337.打家劫舍III

1.题目

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 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. 树的节点数在 [1, 104] 范围内
2. 0 <= Node.val <= 104

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/house-robber-iii

2.解题思路

方法一：动态规划

思路与算法

简化一下这个问题：一棵二叉树，树上的每个点都有对应的权值，每个点有两种状态(选中和不选中)，问在不能同时选中有父子关系的点的情况下，能选中的点的最大权值和是多少。

我们可以用 f(o)f(o) 表示选择 oo 节点的情况下，oo 节点的子树上被选择的节点的最大权值和；g(o)g(o) 表示不选择 oo 节点的情况下，oo 节点的子树上被选择的节点的最大权值和；ll 和 rr 代表 oo 的左右孩子。

1. 当 oo 被选中时，oo 的左右孩子都不能被选中，故 oo 被选中情况下子树上被选中点的最大权值和为 ll 和 rr 不被选中的最大权值和相加，即 f(o)=g(l)+g(r)f(o)=g(l)+g(r)。
2. 当 oo 不被选中时，oo 的左右孩子可以被选中，也可以不被选中。对于 oo 的某个具体的孩子 xx，它对 oo 的贡献是 xx 被选中和不被选中情况下权值和的较大值。故 g(o)=max⁡{f(l),g(l)}+max⁡{f(r),g(r)}g(o)=max{f(l),g(l)}+max{f(r),g(r)}。

至此，我们可以用哈希表来存 ff 和 gg 的函数值，用深度优先搜索的办法后序遍历这棵二叉树，我们就可以得到每一个节点的 ff 和 gg。根节点的 ff 和 gg 的最大值就是我们要找的答案。

3.代码实现

```java class Solution { Map f = new HashMap (); Map g = new HashMap ();

1. public int rob(TreeNode root) {
2.     dfs(root);
3. return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
4. }
5. 
6. public void dfs(TreeNode node) {
7. if (node == null) {
8. return;
9.     }
10.     dfs(node.left);
11.     dfs(node.right);
12.     f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
13.     g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
14. }

}

```