力扣爆刷第77天--动态规划一网打尽打家劫舍问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣爆刷第77天--动态规划一网打尽打家劫舍问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣爆刷第77天–动态规划一网打尽打家劫舍问题

一、198.打家劫舍

题目链接：https://leetcode.cn/problems/house-robber/
思路：小偷不能连续两家偷，由此可以定义dp[i]表示，小偷经过[0,i]所能获取到的最大金额，那么我们可以得到递推公式:
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
即如果偷nums[i]家就不能偷前一家，为dp[i-2]+nums[i]，如果不偷当前这家，那金额就要维持为经过前一家时的结果。
很简单的题目，标准的动态规划，进行状态选择。
标准写法

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

优化写法

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

二、213.打家劫舍II

题目链接：https://leetcode.cn/problems/house-robber-ii/
思路：本题和上一题不同之处是房间首尾相连，那么也很简单，直接从两个范围求，第一个范围[0, len-1]，第二个范围[1, len]，分别从这两个范围，一个只含头，一个只含尾，其他的和上一题一样。

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);
        return Math.max(getMax(nums, 0, nums.length-1), getMax(nums, 1, nums.length));
    }

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

三、337.打家劫舍 III

题目链接：https://leetcode.cn/problems/house-robber-iii/description/
思路：二叉树形态的打家劫舍，其实也很简单，每个节点有两种状态分别是抢不与抢，后序遍历返回dp数组，有了左右子树的dp数组即可计算当前节点的dp数组，计算后返回，以此递归即可解题。文章来源地址https://www.toymoban.com/news/detail-836852.html

/**
 * 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) {
       int[] dp = traverse(root);
       return Math.max(dp[0], dp[1]);
    }
    // 0 偷 1 不偷
    int[] traverse(TreeNode root) {
        if(root == null) return new int[2];
        int[] left = traverse(root.left);
        int[] right = traverse(root.right);
        int[] dp = new int[2];
        dp[0] = root.val + left[1] + right[1];
        dp[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return dp;      
    }
    
}