打家劫舍Ⅰ

题目 ：

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

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

  • 示例 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数组的下标及其含义：

偷窃下标为 i 的房子所能得到的最大金额为dp[i]

  1. 初始化dp数组
1
2
//如果偷窃下标为 0 的 那么得到的最大金额一定为 nums[0]
dp[0] = nums[0];
  1. 确定dp公式
1
2
3
4
5
//对于dp数组来说 ，它的含义就是得到最大金额
//然后我们还有限制条件， 那就是不能偷相邻的房屋 ，所以我们就需要比较偷当前的房子所得的金额大 还是偷下一个房屋得到的金额大

dp[1] = Math.max(dp[0],nums[1]);
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);

这一步挺关键的，那就是考虑怎么偷 ，所以我们在初始化的过程中还要考虑偷第一个还是偷第二个

所以初始化还需要执行一步

1
dp[1] = Math.max(nums[0],nums[1]);
  1. 确定dp的遍历顺序

在本题中，遍历顺序就显得没有之前的考虑的多了，我们只需要将nums数组遍历完即可

1
2
3
for(int i = 2; i< nums.length;i++){
	dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
}
  1. 打印dp数组

如果我们写的逻辑没有问题 ，但是最后答案出现偏差。那么此时就需要打印dp数组，看看那一步没有按照我们的逻辑来。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
	public int rob(int[] nums) {
		if (nums == null || nums.length == 0) return 0;
		if (nums.length == 1) return nums[0];

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

		return dp[nums.length - 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 = [0] 输出：0

提示：

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

思路

​ 本题关键点所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 那么我们就不能单纯按照Ⅰ 的方式去解。

​ 既然他将所有的房屋都连在一起 ，那么我们可以假设出一个分割线 ，通过这个分割线比较两边偷的金额，然后我们取最大值就可以了

**分割线左边 ： **排除第一个房子我们得到的最大金额为dp[i]

**分割线右边 ： **排除最后一个房子我们得到的最大金额为dp[i]

dp五部曲

  1. dp数组的下标及其含义：

偷窃下标为 i 的房子所能得到的最大金额为dp[i]

  1. 初始化dp数组
1
2
//如果偷窃下标为 0 的 那么得到的最大金额一定为 nums[0]
dp[0] = nums[0];
  1. 确定dp公式
1
2
3
4
5
//对于dp数组来说 ，它的含义就是得到最大金额
//然后我们还有限制条件， 那就是不能偷相邻的房屋 ，所以我们就需要比较偷当前的房子所得的金额大 还是偷下一个房屋得到的金额大

dp[1] = Math.max(dp[0],nums[1]);
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);

这一步挺关键的，那就是考虑怎么偷 ，所以我们在初始化的过程中还要考虑偷第一个还是偷第二个

所以初始化还需要执行一步

1
dp[1] = Math.max(nums[0],nums[1]);
  1. 确定dp的遍历顺序

在本题中，遍历顺序就显得没有之前的考虑的多了，我们只需要将nums数组遍历完即可

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

最终代码实现

以力扣的实现为例 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }
        int left = range(nums, 0 , nums.length - 1);
        int right = range(nums, 1, nums.length);
        return Math.max(left, right);
    }
    public int range(int[] nums, int begin, int end){
        if(begin == end- 1 ){
            return nums[begin];
        }
        int[] dp = new int[nums.length];
    
        dp[begin] = nums[begin];
        dp[begin + 1] = Math.max(nums[begin],nums[begin + 1]);
        for(int i = begin + 2;i < end;i++){
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[end - 1];
    }
}

打家劫舍Ⅲ

题目 ：

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

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

337.打家劫舍III

思路

使用原来的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        

        if(root == null) return 0; 
        //选择偷父节点的房子，那么就跳过左右子节点
        int val = root.val;
        if(root.left != null){
            val += rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){
            val += rob(root.right.left) + rob(root.right.right);
        }
        //dp如果没有偷父节点的房子， 那么就可以考虑左右子节点
        int val1 = rob(root.left) + rob(root.right);    
        return Math.max(val, val1);
    }
}

这道题与前面最大的区别就是数据结构使用是树形结构。所以这类题 被称为树形dp。

思路还是一样的，就是不能偷相邻的房子 ，对于树形结构的相邻的房子就是父节点 和 它的两个孩子节点 ，但是兄弟节点之间确是没有相邻。

我们需要先知道它的子节点的大小 ，从而来判断 是否偷当前节点 。所以就需要用后序遍历 ，因为只有这样我们才能先得到子节点 ，然后得到父节点

dp选型

基于递归逻辑使用动归

对于这种类型的题 ，我们的dp数组要做的不仅仅是得到最终的结果 ，还有就是记录每个节点的状态。

dp[0] : 表示 不偷当前节点所得到的最大金额为dp[0]

dp[1] : 表示 偷当前节点所得到的最大金额为dp[1]

  1. 递归的函数 及其参数
1
2
3
4
//这里我们只需要用到dp[0] and dp[1]来记录状态及得到结果
public int[] robot(TreeNode root){
		
}
  1. 确定递归终止条件
1
2
3
if(root == null){
    return new int[]{0,0};
}
  1. 确定递归逻辑
1
2
3
4
5
6
7
8
9
10
11
int left[] = robot(root.left);
int right[] = robot(root.right);
int[] dp = new int[2];
int val = root.val;
//1. 偷当前节点
dp[0] = val + left[0]  + right[0];
//2， 不偷当前节点
//那么就从两个子节点之中选择 一个
dp[1] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
return Math.max(dp[0],dp[1]);

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        //首先定义dp数组为函数的含义
        int[] dp = robot(root);
        return Math.max(dp[0],dp[1]);
    }
        //dp数组的作用就是每个节点的状态 ， 索引为 0 代表不偷当前节点得到的最大金钱为dp[0]
        // 索引为1 代表投当前节点得到的最大金钱为 dp[1]
    public int[] robot(TreeNode root){
        if(root == null){
            return new int[]{0,0};
        }
        int val = root.val;
        int[] left = robot(root.left);
        int[] right = robot(root.right);

        //如果偷当前节点 ，那么就不偷它的子节点
        val = val + left[0] + right[0];
        //如果不偷当前节点的钱， 那么就从它的子节点中找出最大的金钱数去偷一个
        int val1 = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
        return new int[]{val1,val};
    }
}