动态规划part7｜198.打家劫舍、213.打家劫舍II、337.打家劫舍III

198. 打家劫舍 🔗：198. 打家劫舍 - 力扣（LeetCode）思路：比较简单的动态规划。 一开始没考虑到【2，1，1，2】这种情况应该怎么处理，对于amount[1]的初始化有些问题 代码： class Solution { public int rob(int[] nums) { // if(nums.length==1) return nums[0]; int[] amount = new int[nums.length]; amount[0] = nums[0]; // 初始化 amount【1】出错 amount[1] = Math.max(nums[0],nums[1]); for(int i=2; i<nums.length; i++){ amount[i] = Math.max(amount[i-2]+nums[i],amount[i-1]); } return amount[nums.length-1]; } } 213.打家劫舍II 🔗：213. 打家劫舍 II - 力扣（LeetCode）思路： 分类讨论，一开始想到了考虑打劫第一个和不打劫第一个需要分开来考虑。但是始终想把他们俩合并到一起考虑，没有想到办法，最后发现实际上官方题解就是用分类的方式。写的没有官方题解简洁，可以抽象成同一个方法来调用。 代码： class Solution { public int rob(int[] nums) { int[] amount = new int[nums.length]; // 长度为1、2的情况 amount[0] = nums[0]; if(nums.length==1) return amount[0]; amount[1] = Math.max(nums[0],nums[1]); if(nums.length==2) return amount[1]; // case1:打劫第一间房 for(int i=2; i<nums.length-1; i++){ amount[i] = Math.max(nums[i]+amount[i-2],amount[i-1]); }//1+3=4 int case1amount = amount[nums.length-2]; // case2: 不打劫第一间房 amount[1] = nums[1]; amount[2] = Math.max(nums[1],nums[2]); for(int i=3; i<nums.length; i++){ amount[i] = Math.max(nums[i]+amount[i-2],amount[i-1]); } int case2amount = amount[nums.length-1]; return Math.max(case1amount,case2amount); } } 337.打家劫舍III 🔗：337. 打家劫舍 III - 力扣（LeetCode）思路： 非常巧妙的思路。一开始自己写的没有通过第60个用例，没有考虑到【2，1，1，2】这种情况，反了和今日第一题一样的问题，后来照着官方题解的写了一下。节点可以有两个状态：selected & not selected select：则左右子节点均不能被选择not selected：左右子节点可以被选择，也可以不被选择 代码： class Solution { public int rob(TreeNode root) { int[] rootStatus = traverse(root); return Math.max(rootStatus[0], rootStatus[1]); } public int[] traverse(TreeNode root){ if(root==null) return new int[]{0,0}; int[] l = traverse(root.left); int[] r = traverse(root.right); // 当node被选中时，left和right一定不被选中 // 所以selected = node的值+left&right不被选中的值 int selected = root.val + l[1]+r[1]; // 当node不被选中时，left和right可以被选中，也可以不被选中 // 因此选取他们的最大值 int notSelected = Math.max(l[0],l[1])+Math.max(r[0],r[1]); return new int[]{selected,notSelected}; } }