Day 48 | 198.打家劫舍 & 213.打家劫舍II & 337.打家劫舍 III

198.打家劫舍

 动态规划解题思路：

①确定dp数组以及下标含义

        dp[i]：偷窃到第i号房屋能偷窃到的金额为dp[i]

②确定递推公式

每到一个房屋，有两个选择

        1 不偷：则dp[i]=dp[i-1] （等于前一号房屋偷的最大金额）

        2 偷：则dp[i]=dp[i-2]+nums[i] （等于到i-2号房屋偷得最大金额加上当前房屋的金额）

本题求的是最大金额，因此

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

③dp数组如何初始化

        dp[0]=nums[0] 即一号房屋金额

        dp[1]=Math.max(dp[0],dp[1]) 两者取大值，二号房屋金额若没一号房屋多，则选择不偷即可。

④确定遍历顺序

           dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]; dp[i]由前面i-1决定，因此从前向后遍历

⑤举例推导dp数组

    public int rob(int[] nums) {
        int[] dp = new int[nums.length ];
        if(nums.length==1){return nums[0];}
        if(nums.length==0){return 0;}
        dp[0] = nums[0];
        dp[1] = Math.max(nums[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];
    }

213.打家劫舍II

动态规划解题思路： 

         对于本题，和第一题的区别就是第一个房间和最后一个房间不能重复偷。

情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了。

因此分两种情况：

        ①偷第一间房，偷窃范围为[0,i-2]          

        ②偷最后一间房，偷窃范围为[1,i-1]

        我一开始想是否要标记第一个房间偷没偷过，发现想复杂了。因为第一个房间如果没被偷，该情况已经在第二种情况下被包含了。如果最后一间房没被偷，该情况也在第一种情况被包围了，最后都是取最大值，因此不影响最终结果。

        和第一题一样，只不过加入多定义一个函数设置起始和终止下标，最后判断哪个下标范围偷得金额多返回即可。

class Solution {
    public int rob(int[] nums) {
        int a=rob(nums,0, nums.length-2);
        int b=rob(nums,1, nums.length-1);
        return a>b?a:b;
    }
 
    public static int rob(int[] nums,int start,int end) {
        int[] dp = new int[nums.length];
        if(nums.length==1){return nums[0];}
        if(nums.length==0){return 0;}
        if(start==end){return nums[start];}
        dp[start] = nums[start];
        dp[start+1] = Math.max(nums[start+1], nums[start]);
        for (int i = start+2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }
}

337.打家劫舍 III

树形动态规划解题思路：

本题是树形动态规划问题，采用递归方法后序遍历树上的节点，将偷到的钱记录在dp数组中，

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

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

下标为0代表不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

dp[0]:Math.max(left[0],left[1])+Math.max(right[0],right[1]); 

 //选择偷或不偷左节点的大值，偷或不偷右节点的大值

dp[1]:root.val+right[0]+left[0];

//偷当前节点，不偷左右孩子节点

直到遍历到空节点代表树遍历完成，返回dp数组，最后结果即为dp[0]和dp[1]中的较大值。

class Solution {
    public int rob(TreeNode root) {
        int[] a=robAction(root);
        return Math.max(a[0],a[1]);
    }
 
    public int[] robAction(TreeNode root){
        int[] res=new int[2];
        if(root==null){
            return res;
        }
 
        //后序遍历
        int[] left=robAction(root.left);
        int[] right=robAction(root.right);
        //不偷自己偷孩子
        res[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        res[1]=root.val+right[0]+left[0];
 
        return res;
    }
}