DP(7) | 打家劫舍① | Java | LeetCode 198, 213, 337 做题总结（未完）

打家劫舍问题

来源于代码随想录：https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html#%E6%80%9D%E8%B7%AF

① 确定dp数组（dp table）以及下标的含义
dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

② 确定递推公式
决定dp[i]的因素就是第i房间偷还是不偷。

• 偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

• 不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）

然后dp[i]取最大值， 即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

③ dp数组初始化
从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]

从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

④ 确定遍历顺序
dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历

⑤ 举例推导dp数组（略）

198.打家劫舍

class Solution {public int rob(int[] nums) {if(nums.length == 1) return nums[0];int[] dp = new int[nums.length+1];dp[0] = nums[0];dp[1] = nums[0]>nums[1]?nums[0]:nums[1];for(int i=2; i<nums.length; i++) {dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);}return dp[nums.length-1];}
}

213.打家劫舍II

和打家劫舍1区别在，成环-首尾相连
因为首元素和尾元素不能同时存在，所以有三种情况。

三个情况
①不考虑首元素也不考虑尾元素
②考虑首不考虑尾：相当于没有尾元素
③考虑尾不考虑首：
注意情况②③是包含情况①的

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(robAction(nums,0,nums.length-2), robAction(nums,1,nums.length-1));}public int robAction(int[] nums, int start, int end) {int len = end-start+1;int[]dp = new int[len]; //end-start+1长度dp[0] = nums[start];dp[1] = Math.max(dp[0], nums[start+1]);for(int i=2; i<len; i++) {dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i+start]);}return dp[len-1];}
}

出错点

dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i+start]); dp数组的下标是从0开始，但是nums数组的取值要加上start

337.打家劫舍III