丰城市城乡规划建设局网站,网站的建设宗旨,在哪个网站上做外贸好,做dnf辅助网站一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。 给定一个代表每个房屋存放金额的非负… 一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组 nums 请计算 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 输入nums [1,2,3,1]
输出4
解释偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。偷窃到的最高金额 1 3 4 。 如上图每个房间放的金子都不同有多有少两个房间之间有警报相连如果同时偷取相连的两个房子警报就会发出你就要去蹲局子那么如何做一个聪明的小偷在不触发警报的情况下偷取的金额是最大的接下来让我们替小偷想一个方案如何去偷
我们可以从后往前考虑假如我们偷取最后一间房间 我们是不是不可以偷取倒数第二间房间可供的选择就是在倒数第二间之后随便选一家进行偷取 为了利益最大化我们是不是应该偷取的是前n-2间房子的最大金额数最后一间房子的最大金额数就是我们当前可以偷取的最大金额数呢NONONO,我们还有一种不偷取最后一间房子的情况偷取n-2房间的情况 我们通过上述的推导就可以将动态转移方程写出来 dp[i]Math.max(dp[i-1],nums[i]dp[i-2]);
我们设置的dp数组的语意是dp[i]是偷取第i家的最大金额数 我们可以很简单的推导出基本情况如果没有房间小偷就得被饿死如果只有一家小偷无可奈何只能被迫的去偷这家如果有两家小偷肯定回去偷金额比较多的那家 dp[0]nums[0];dp[1]Math.max(nums[0],nums[1]);
解题的入参判断肯定少不了这种入参判断能为你解决不少的麻烦 if(n0){return 0;}if(n1){return nums[0];}
那么我们的代码 就已经写完了
public int rob(int[] nums) {int nnums.length;if(n0){return 0;}if(n1){return nums[0];}int [] dpnew int[n];dp[0]nums[0];dp[1]Math.max(nums[0],nums[1]);for(int i2;in;i){dp[i]Math.max(dp[i-1],nums[i]dp[i-2]);}return dp[n-1];} 打家劫舍II的基本过程和I差不多就是从一个直线型房屋排列转换为环形房屋排列这种就应该考虑是n-1房子和0房子偷不偷的问题其实可以分为两个数组分别计算可以偷取的最大金额最后取最大值就ok了我们下面讲打家窃舍III 我不得不说这小偷的数据结构学的其实蛮好的什么样的房屋排列都能让他想到数据结构这块利用算法的知识进行解决不当码农可惜了 来让我们言归正传 对于我们的选择是每个节点是否偷取决定着我们最后的结果 如果偷的话情况又是如何不偷的时候情况又是怎样的 看到这幅图大家会想到什么树的层序遍历但是树的层序遍历在这里可是不适用的因为这道题中的有些情况是通过不了所以我们换种思维想一想这种题是不是可以用递归的方式解决 假设我们的当前节点是root,递归函数是rob
偷当前的节点的金额数rob(节点左树的子左树)rob(节点左树的右树)rob(节点右树的左树)rob(节点右树的右树)
不偷rob(节点的左树)rob(节点的右树) int robroot.val(root.leftnull?0:rob(root.left.left)rob(root.left.right))(root.rightnull?0:rob(root.right.right)rob(root.right.left));int rob_notrob(root.left)rob(root.right); 这种递归大概率会超时所以我们加一个记忆化数组不用再进行重复计算进行剪枝 MapTreeNode,Integer mapnew HashMap();if(map.containsKey(root)){return map.get(root);} 该题的大致流程就已经讲完了希望大家可以看的开心不懂的可以在评论区问我我看到的话会给大家一一解答 MapTreeNode,Integer mapnew HashMap();public int rob(TreeNode root) {if(rootnull){return 0;}if(map.containsKey(root)){return map.get(root);}int robroot.val(root.leftnull?0:rob(root.left.left)rob(root.left.right))(root.rightnull?0:rob(root.right.right)rob(root.right.left));int rob_notrob(root.left)rob(root.right);int maxMath.max(rob,rob_not);map.put(root,max);return max;}
