198.打家劫舍
题目链接：198.打家劫舍
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰打家劫舍
日期：2024-10-13
想法：dp[i]到第i个房子时能偷的最多的钱；递推公式：是上上一栋房子的dp[i - 2]加上这栋房子的钱nums[i]大还是上一家邻居偷的钱dp[i - 1]的大；初始化因为有i - 2；所以初始化dp[0]和dp[1]；顺序，从前往后；打印。
Java代码如下：
class Solution {public int rob(int[] nums) {if(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(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];}
}
213.打家劫舍II
题目链接：213.打家劫舍II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰打家劫舍II
日期：2024-10-13
想法：因为首尾相连，所以nums得分两种情况，要头不要尾和要尾不要头，rob1(nums, 0, nums.length - 2)和rob1(nums, 1, nums.length - 1)这两种，注意start = end的时候要返回nums[start]
Java代码如下：
class Solution {public int rob1(int[] nums, int start, int end) {if(start == end) return nums[start];int[] dp = new int[nums.length];dp[start] = nums[start];dp[start + 1] = Math.max(nums[start], 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];}public int rob(int[] nums) {if(nums.length == 0) return 0;if(nums.length == 1) return nums[0];int res1 = rob1(nums, 0, nums.length - 2);int res2 = rob1(nums, 1, nums.length - 1);return Math.max(res1, res2);}
}
337.打家劫舍III
题目链接：337.打家劫舍III
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰打家劫舍III
日期：2024-10-13
想法：dp[0]表示不抢当前节点的最大钱，dp[1]为抢，后序遍历。
Java代码如下：
class Solution {public int rob(TreeNode root) {int[] dp = rob1(root);return Math.max(dp[0], dp[1]);}public int[] rob1(TreeNode root) {int[] dp = new int[2];if(root == null) return dp;int[] left = rob1(root.left);int[] right = rob1(root.right);dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);dp[1] = root.val + left[0] + right[0];return dp;}
}
