代码随想录算法训练营第三十九天 | 198-打家劫舍、213-打家劫舍Ⅱ、337-打家劫舍Ⅲ
LeetCode198 打家劫舍
题目链接：https://leetcode.cn/problems/house-robber/
文章讲解：https://programmercarl.com/0198.打家劫舍.html
视频讲解：https://www.bilibili.com/video/BV1Te411N7SX/?vd_source=b989f2b109eb3b17e8178154a7de7a51
打家劫舍问题，动规五部曲：
- 确定dp数组以及下标的含义
考虑下标i，偷到的最大金额为dp[i]
- 确定递推公式
偷i房间：dp[i] = dp[i-2] + coins[i]
不偷i房间：dp[i] = dp[i-1]
状态转移方程：dp[i] = Math.max(dp[i-2] + coins[i]，dp[i-1])
- dp数组如何初始化
由状态转移方程可以看出，dp[i]是由dp[i-1]和dp[i-2]推出来的，因此dp[0]和dp[1]要进行初始化，dp[0] = coins[0]，dp[1] = Math.max(coins[0]，coins[1])
- 确定遍历顺序
一层for循环，从下标2开始往后遍历coins数组
- 举例推导dp数组
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];}
}
LeetCode213 打家劫舍Ⅱ
题目链接：https://leetcode.cn/problems/house-robber-ii/description/
文章讲解：https://programmercarl.com/0213.打家劫舍II.html
视频讲解：https://www.bilibili.com/video/BV1oM411B7xq/?vd_source=b989f2b109eb3b17e8178154a7de7a51
打家劫舍问题，但是这题coins数组成环，因此要分成两种情况考虑：①包含首元素且不包含尾元素的coins数组、②包含尾元素且不包含首元素的coins数组，两种情况分别套用打家劫舍的经典算法得到result1和result2，取二者中最大值即为题解
动规五部曲：
- 确定dp数组以及下标的含义
考虑下标i，偷到的最大金额为dp[i]
- 确定递推公式
偷i房间：dp[i] = dp[i-2] + coins[i]
不偷i房间：dp[i] = dp[i-1]
状态转移方程：dp[i] = Math.max(dp[i-2] + coins[i]，dp[i-1])
- dp数组如何初始化
由状态转移方程可以看出，dp[i]是由dp[i-1]和dp[i-2]推出来的，因此dp[0]和dp[1]要进行初始化，dp[0] = coins[0]，dp[1] = Math.max(coins[0]，coins[1])
- 确定遍历顺序
一层for循环，从下标2开始往后遍历coins数组
- 举例推导dp数组
class Solution {public int rob(int[] nums) {if(nums.length == 1){return nums[0];}int[] nums1 = Arrays.copyOfRange(nums, 0, nums.length-1);int[] nums2 = Arrays.copyOfRange(nums, 1, nums.length);int result1 = classicRobber(nums1);int result2 = classicRobber(nums2);return Math.max(result1, result2);}public int classicRobber(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];}
}
LeetCode337 打家劫舍Ⅲ
题目链接：https://leetcode.cn/problems/house-robber-iii/
文章讲解：https://programmercarl.com/0337.打家劫舍III.html
视频讲解：https://www.bilibili.com/video/BV1H24y1Q7sY/?spm_id_from=333.1391.0.0&vd_source=b989f2b109eb3b17e8178154a7de7a51
打家劫舍问题，二叉树结构，树形dp
每个节点只有偷和不偷两种状态，用长度为2的一维数组，dp[0]表示不偷当前节点获得的最大金钱，dp[1]表示偷当前节点获得的最大金钱。遍历二叉树时，每一层递归都有一个dp数组，当前层的dp数组表示当前层状态
采用后序遍历，从底向上，先求得左右孩子的dp数组，再求根节点的dp数组
如果遇到空节点，return {0，0}
偷i房间：val1 = curNode.val + leftdp[0] + rightdp[0]
不偷i房间：val2 = Math.max(leftdp[0], leftdp[1]) + Math.max(rightdp[0]，rightdp[1])
return {val1，val2}
/*** 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 = postOrder(root);return Math.max(dp[0], dp[1]);}public int[] postOrder(TreeNode curNode){int[] records = new int[2];if(curNode == null){return records;}int[] leftdp = postOrder(curNode.left);int[] rightdp = postOrder(curNode.right);records[1] = curNode.val + leftdp[0] + rightdp[0];records[0] = Math.max(leftdp[0], leftdp[1]) + Math.max(rightdp[0], rightdp[1]);return records;}
}