力扣打家劫舍1-3 java实现

打家劫舍Ⅰ

思路 动态规划实现，只需要隔着偷就好。

class Solution {
          
   
    public int rob(int[] nums) {
          
   
        int n = nums.length;
        // 处理边界条件。
        if (n == 0) {
          
   
            return 0;
        }
        if (n == 1) {
          
   
            return nums[0];
        }
        // 定义dp数组，按照状态转移方程递推。
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = nums[0];
        //dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i <=n; i++) {
          
   
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i-1]);
        }
        return dp[n];
    }
}

在这里可以做一个优化，方程dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i-1])中的dp[i-1]和dp[i-2]可以使用常量进行替代，只需要在每次赋值之后再更新常量即可。

class Solution {
          
   
    public int rob(int[] nums) {
          
   
        int a = 0, b = 0;
        for (int i = 0; i < nums.length; i++) {
          
   
            int c = Math.max(b, a + nums[i]);
            a = b;
            b = c;
        }
        return b;
   }
}

打家劫舍Ⅱ

思路 Ⅱ跟Ⅰ的差别就是第一个和最后一个不能同时偷，那么可以考虑第一个偷，最后一个不偷 和 第一个不偷（最后一个无所谓偷不偷）的情况。

class Solution {
          
   
    public int rob(int[] nums) {
          
   
        /*
        整体思路就是把圈转化成线，把问题转化成打家劫舍1去做，分为不偷第一栋和不偷最后一栋去做
        */
        int n=nums.length;
        if(n==0) return 0;
        if(n==1) return nums[0];
        int []dp=new int[n+1];
        //偷第一个不偷最后一个
        dp[0]=0;
        dp[1]=nums[0];
        for(int i=2;i<=n;i++){
          
   
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        int end=dp[n-1];
        //不偷第一个
        dp[1]=0;
        for(int i=2;i<=n;i++){
          
   
            dp[i]= Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return Math.max(end,dp[n]);
    }
}

打家劫舍Ⅲ

思路 二叉树结构想办法用递归吧，这种情况无非就是要么偷四个孙子+根结点，要么偷两个左右结点，递归实现。

public int rob(TreeNode root) {
          
   
    if (root == null) return 0;
    int money = root.val;
    if (root.left != null) {
          
   
        money += (rob(root.left.left) + rob(root.left.right));
    }

    if (root.right != null) {
          
   
        money += (rob(root.right.left) + rob(root.right.right));
    }

    return Math.max(money, rob(root.left) + rob(root.right));
}

最简单粗暴的实现了，提交结果发现效率当然不会很高，应该是可以改进的，参考了别人的思路，确实很有想法。

class Solution {
          
   
    public int rob(TreeNode root) {
          
   
        int []res=helper(root);
        return Math.max(res[0],res[1]);
    }
    public int[] helper(TreeNode root){
          
   
        //数组下标0存储的不抢劫当前结点可获得的最大金额，1存储的是抢劫当前结点可获得最大金额
        if(root== null) return new int[2];//边界条件，r为null时，跳出
        int[] left=helper(root.left);//对于以root.left为根的树，计算抢劫根节点(root.left)与不抢劫根节点可获得最大金额. left[0]则为不抢root.left可获得的最大金额,left[1]则为抢劫root.left可获得的最大金额
        int[] right=helper(root.right);
        int []res=new int[2];
        res[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        res[1]=root.val+left[0]+right[0];
        return res;
    }
}

参考资料：