打家劫舍问题

打家劫舍一:

代码随想录链接:代码随想录

题目内容:

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

思路:

(1).确定dp数组的形式以及其表示的含义:

dp数组的长度为房屋数组的长度，其中每个元素dp[i]表示考虑下标i(包括i)以内的房屋，最多可以偷窃的金额为dp[i]

(2).确定dp数组的递推公式:

可以看出，dp[i]有两种求解方法

第一种:从第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公式为dp[i] = max(dp[i-1],dp[i-2]+nums[i]);

(3).dp数组如何初始化

根据递推公式，可以看出dp数组需要初始化dp[0]和dp[1]

其中dp[0] = nums[0],dp[1] = max(nums[1],nums[0]);

(4).确定遍历顺序

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

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];
	}
}

打家劫舍二:

代码随想录链接:代码随想录

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额

思路:

采用打家劫舍一的思路，需要依次不考虑数组的头元素和尾元素，分别求出两种情况下对应的结果，最终取这两个值中的较大值即可

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==1){
            return nums[0];
        }
        int[] dp1 = new int[n-1];
        int[] dp2 = new int[n-1];
        for(int i = 0;i<n-1;i++){
            if(i==0){
                dp1[i] = nums[0];
            }else if(i==1){
                dp1[i] = Math.max(nums[0],nums[1]); 
            }else{
                dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i]);
            }
        }
        for(int i = 1;i<n;i++){
            if(i==1){
                dp2[i-1] = nums[1];
            }else if(i==2){
                dp2[i-1] = Math.max(nums[i],nums[i-1]);
            }else{
                dp2[i-1] = Math.max(dp2[i-2],dp2[i-3]+nums[i]); 
            }
        }
        return Math.max(dp1[n-2],dp2[n-2]);

    }
}

打家劫舍三:

代码随想录链接:代码随想录

题目描述:

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

思路:

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

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

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

结合递归方法与动态规划求解问题

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

要求一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组,参数为当前节点

其实这里的返回数组就是dp数组,dp数组(dp table)下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱

(2).确定终止条件

在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以直接返回dp数组即可

(3).确定遍历顺序

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

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

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

(4).确定单层递归的逻辑

对于一个非空的节点，存在两个状态，分别是偷与不偷

其中，当偷该节点时，该节点的两个子节点无法偷，因此dp[1] = root.value + left[0] + right[0];

当不偷该节点时，该节点的两个子节点可以偷也可以不偷，此时dp[0]的取值为左节点偷与不偷的最大金钱和右节点偷与不偷的最大金钱之和 

因此dp[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);

最后当前节点的状态就是{dp[0], dp[1]}; 即{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

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

Java代码:

public int rob3(TreeNode root) {
    int[] res = robAction1(root);
    return Math.max(res[0], res[1]);
}

int[] robAction1(TreeNode root) {
    int res[] = new int[2];
    if (root == null)
       return res;
    int[] left = robAction1(root.left);
    int[] right = robAction1(root.right);
    res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    res[1] = root.val + left[0] + right[0];
    return res;
    }
}