DP4

2020-05-12

打家劫舍问题总结

首先声明一点，我不一定会选择最优的解法，但是我一定会选择最容易理解的做法

事实上，在dp问题的优化上，我们也只能够优化空间复杂度，即dp问题的时间复杂度是固定的
而且一般最优解法比较难想，所以我们先从最容易理解的做法开始

LeetCode 198、打家劫舍 https://leetcode-cn.com/problems/house-robber/

当我们看到这个题目的时候，首先可以看出这是一个0-1背包问题，即我们只用考虑选不选择最后一个房屋即可.
那么状态转移方程可以很容易的写出来 dp[i]=max{dp[i-1],dp[i-2]+nums[i]}

class Solution {
    public int rob(int[] nums) {
          if(nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        int n=nums.length;
        int dp[]=new int [n+1];
        //dp[0]代表只有一间房屋
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<n;i++){
          //dp[i-1]代表不选择最后一间房屋，那么另外一种情况就是选择最后一间房屋
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
}

LeetCode 213、打家劫舍2 https://leetcode-cn.com/problems/house-robber-ii/

此问题与第一版不同，此时是一个环，而不是一条直线，这就意味着我们在选择第一家时，就不能选择最后一家。
同理，我们如果选择了最后一家，那么就不能选择最后一家。
那么我们可以分两种情况，这时就有一个有趣的地方，以往我们在做dp问题时都是一个dp数组，一维或者二维，现在这里我们可以分为两个dp数组，比较直观

class Solution {
    public int rob(int[] nums) {
        //处理边界
           if(nums.length==0) return 0;
        int n=nums.length;
        if(n==1) return nums[0];
        if(n==2) return Math.max(nums[0],nums[1]);
        if(n==3) return Math.max(Math.max(nums[0],nums[1]),nums[2]);
        //如果我们选择第一家，不选最后一家
        int []dp1=new int[n+1];
        //这里选择了第一家，即只能抢劫第一家
        dp1[0]=nums[0];
        dp1[1]=nums[0];
        //由于不选择最后一家，我们直接将最后一种情况舍弃
        for(int i=2;i<n-1;i++){
            dp1[i]=Math.max(dp1[i-1],dp1[i-2]+nums[i]);
        }
        
        //如果我们不选第一家，选择最后一家
        int dp2[]=new int[n+1];
        //不选第一家，那么前两个只能选择第二个
        dp2[0]=0;
        dp2[1]=nums[1];
        for(int i=2;i<n;i++){
            dp2[i]=Math.max(dp2[i-1],dp2[i-2]+nums[i]);
        }
        
        //同样的，这里在返回时也应该注意
        return  Math.max(dp1[n-2],dp2[n-1]);
    }
}

我们可以看出，上题还是有很多细节的，如果有些地方稍微写错，那么就跑不出我们想要的答案.

接下来我们来到最后一个问题

LeetCode 337、打家劫舍3 https://leetcode-cn.com/problems/house-robber-iii/

这题也很有意思，让强盗在一棵二叉树上进行打劫，并且不能选择两个相邻的节点，这里的相邻是指他们之间有连接.
这里运用到了一个比较巧妙的思想，直接看代码

class Solution {
    public int rob(TreeNode root) {
        int[] res=dp(root);
        return Math.max(res[0],res[1]);
    }
    //返回一个大小为2的数组，其中第一个数代表不抢根节点，第二个数代表抢根节点
    private int[] dp(TreeNode root){
        if(root==null) return new int[]{0,0};
        int left[]=dp(root.left);
        int right[]=dp(root.right);
        //抢根节点，那么就不能抢根节点下一个数
        int rob=root.val+left[0]+right[0];
        //不抢根节点
        int not_rob=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        return new int[]{not_rob,rob};
    
    }
}

在这里我们非常巧妙的运用了递归，事实上，与树的很多问题我们都可以用递归来解决，在利用递归时，我们不必去考虑实现的细节，在本题中，我们不必去考虑左右子树的遍历过程。而只用考虑是否选择根节点即可

从打家劫舍1-3题，我们实现了从数组->环->树的进阶。

本篇中我所提供的代码不一定是最优解，但是一定是最容易理解的解！