做网站做网站,网站添加备案号,网站基础风格创建,企业网站如何做推广本章汇总一下leetcode中的打家劫舍问题#xff0c;使用经典动态规划算法求解。
1、梦开始的地方——打家劫舍#xff08;★#xff09; 本题关键点就是不能在相邻房屋偷东西。
采用常规动态规划做法#xff1a;
根据题意设定dp数组#xff0c;dp[i]的含义为#xff1a… 本章汇总一下leetcode中的打家劫舍问题使用经典动态规划算法求解。
1、梦开始的地方——打家劫舍★ 本题关键点就是不能在相邻房屋偷东西。
采用常规动态规划做法
根据题意设定dp数组dp[i]的含义为前i个房屋内能偷的最高金额。需要初始化dp[0]0dp[1]nums[0]。遍历dp数组对应两种情况偷或者不偷。 递推公式为 dp[i] Math.max(dp[i-1] , dp[i-2]nums[i-1]); 最后返回dp数组最后一个数。
java代码如下
class Solution {public int rob(int[] nums) {if(nums.length 1) return nums[0];int[] dp new int[nums.length1]; //dp[i]:前i个房屋内能偷的最高金额。dp[1] nums[0];for(int i2; inums.length; i){dp[i] Math.max(dp[i-1] , dp[i-2]nums[i-1]); //分别对应偷或者不偷}return dp[nums.length];}
}
2、打家劫舍II 本题是上一题的进阶版区别在于收尾两个房屋也是相邻的不能同时偷。 此时无非就两种情况
不偷首房屋。不偷尾房屋。 分别设两个dp数组对应以上两种情况即可思路还是类似上一题。
java代码如下
class Solution {public int rob(int[] nums) {if(nums.length 1) return nums[0];int[] dp1 new int[nums.length]; //不偷首房屋int[] dp2 new int[nums.length]; //不偷尾房屋dp1[1] nums[1];dp2[1] nums[0];for(int i2; inums.length; i){dp1[i] Math.max(dp1[i-1] , dp1[i-2]nums[i]);dp2[i] Math.max(dp2[i-1] , dp2[i-2]nums[i-1]);}return dp1[nums.length-1] dp2[nums.length-1] ? dp1[nums.length-1] : dp2[nums.length-1];}
}
3、打家劫舍III★ 本题是从数组型dp转化为树形dp由于父节点的状态需要从孩子节点的状态推出来因此需要使用后序遍历。 首先需要定义一个递归函数dfs参数为当前节点返回值为长度为2的数组即dp数组dp[0]代表选当场节点dp[1]代表不选当前节点。 如下 int[] dfs(TreeNode node) 接下来确定终止条件 if(node null) return new int[] {0,0}; 使用后序遍历递归遍历左右子树 //递归左右子树 int[] left dfs(node.left); int[] right dfs(node.right); 确定单层递归逻辑 //分别对应偷与不偷的情况 int rob node.val left[1] right[1]; int no_rob Math.max(left[0],left[1]) Math.max(right[0],right[1]); java代码如下
/*** 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[] ans dfs(root);return Math.max(ans[0],ans[1]);}private int[] dfs(TreeNode node){if(node null) return new int[] {0,0};//递归左右子树int[] left dfs(node.left);int[] right dfs(node.right);int rob node.val left[1] right[1];int no_rob Math.max(left[0],left[1]) Math.max(right[0],right[1]);return new int[] {rob,no_rob};}
}
