代码随想录算法训练营第52天（动态规划09 ● 198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

今天就是打家劫舍的一天，这个系列不算难，大家可以一口气拿下。

198.打家劫舍

题目链接： 198.打家劫舍
视频讲解： 198.打家劫舍
文章讲解： 198.打家劫舍

解题思路

递归五部曲

1. 确定dp数组以及下标的含义
   dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
2. 确定递推公式
   dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
3. dp数组如何初始化
   递推公式的基础就是dp[0] 和 dp[1]
   dp[0] = nums[0]，dp[1] = max(nums[0], nums[1]);
4. 遍历顺序
   从前到后
5. 举例推导dp数组

// 动态规划
class Solution {public int rob(int[] nums) {if(nums == null || nums.length == 0) return 0;if(nums.length == 1) return nums[0];int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(dp[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];}
}

213.打家劫舍II

题目链接： 213.打家劫舍II
视频讲解： 213.打家劫舍II
文章讲解： 213.打家劫舍II

解题思路

对于一个数组，成环的话主要有如下三种情况：
情况一：考虑不包含首尾元素
情况二：考虑包含首元素，不包含尾元素
情况三：考虑包含尾元素，不包含首元素
而情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了。
分析到这里，剩下的和198.打家劫舍就是一样的了。

class Solution {public int rob(int[] nums) {if(nums == null || nums.length == 0) return 0;if(nums.length == 1) return nums[0];return Math.max(robAction(nums, 0, nums.length - 1), robAction(nums, 1, nums.length));}int robAction(int[] nums, int start, int end) {int dp3 = 0;int dp2 = 0;int dp1 = 0;for(int i = start; i < end; i++){dp1 = dp3;dp3 = Math.max(dp1, dp2 + nums[i]);dp2 = dp1;}return dp3;}// 运行没通过 不知道为啥// int robAction(int[] nums, int start, int end) {//     int[] dp = new int[nums.length];//     dp[start] = nums[start];//     dp[start + 1] = Math.max(dp[0], nums[start + 1]);//     for(int i = start + 2; i < end; i++){//         dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);//     }//     return dp[end - 1];// }
}

337.打家劫舍III

题目链接： 337.打家劫舍III
视频讲解： 337.打家劫舍III
文章讲解： 337.打家劫舍III

解题思路

动态规划和二叉树的结合
动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。
递归三部曲

1. 确定递归函数的参数和返回值
   长度为2的dp数组
   dp[0]0记录不偷该节点所得到的的最大金钱，dp[1]1记录偷该节点所得到的的最大金钱。
2. 确定终止条件
   在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回
3. 确定遍历顺序
   首先明确的是使用后序遍历。 因为要通过递归函数的返回值来做下一步计算。
   通过递归左节点，得到左节点偷与不偷的金钱。
   通过递归右节点，得到右节点偷与不偷的金钱。
4. 确定单层递归的逻辑
   如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就再回顾一下dp数组的含义）
   如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
   最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
5. 举例推导dp数组

 // 动态规划
class Solution {public int rob(TreeNode root) {int[] res = robAction(root);return Math.max(res[0], res[1]);}int[] robAction(TreeNode root){int res[] = new int[2]; // res[0] 代表不偷时的价值 res[1]代表偷的时候的价值// 终止递归条件if(root == null){return res;}// 后序遍历// 左右int[] left = robAction(root.left);int[] right = robAction(root.right);// 中res[0] = Math.max(left[0], left[1]) +Math.max(right[0], right[1]);res[1] = root.val + left[0] + right[0];return res;}
}