网站建设 软件开发阿里云服务器官方网站

力扣爆刷第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数组，计算后返回，以此递归即可解题。

/*** 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;      }}