leetcode198,213 house robber

whidy 发布于2019-08-16 11:01 / 2223人阅读

摘要：你不能连着偷两家因为这样会触发警报系统。现在有一个数组存放着每一家中的可偷金额，问可以偷的最大金额为多少这里考验了动态编程的思想。动态编程要求我们将问题一般化，然后再找到初始情况开始这个由一般到特殊的计算过程。

House Robber I

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, 
the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police 
if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, 
determine the maximum amount of money you can rob tonight without alerting the police.

假设你现在是一个小偷，想要一整条街上的人家。你不能连着偷两家因为这样会触发警报系统。现在有一个nums数组存放着每一家中的可偷金额，问可以偷的最大金额为多少？

这里考验了动态编程的思想。动态编程要求我们将问题一般化，然后再找到初始情况开始这个由一般到特殊的计算过程。
我们先考虑一般情景，假设已经经过了i-1户人家，现在决定是否要偷第i家，
有两种选择：偷 or 不偷
如果偷的话，就意味着前一户人家不能偷，因此我们需要知道前一户人家不偷的话我们可以获得的最大收益，也就是rob=notRub+nums[i]
如果不偷的话，就意味着着前一户人家可以是偷过或者没有偷过，那么我们只需要保留二者的最大值就可以了，也就是notRob = max(rob, notRob)
在这个基础上，我们来寻找一般情况，也就是第一次作案时候的选择，则rob=nums[0],notRob=0

现在来举一个具体的例子，假设我现在nums的值为[4,2,3,9]，我们按照上面的思路，将rob和notRob分别初始化为4和0，则rob和notRob的变化如下
rob : notRob
4 : 0
2 : 4
7 : 4(max(2,4))
13 : 7
则可以获得最大值为13

代码如下：

    public int rob(int[] nums) {
        if(nums==null || nums.length ==0) return 0;
        //抢劫了前一个房子可以获得的最大收入
        int rob = nums[0];
        //没有抢劫前一个房子可以获得的最大收入
        int notRob = 0;
        for(int i = 1 ; i
House Robber II
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. 
This time, all houses at this place are arranged in a circle. 
That means the first house is the neighbor of the last one. 
Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, 
determine the maximum amount of money you can rob tonight without alerting the police.
和第一题需求的区别在于，这个街区的房子为环形的。也就是说首尾的房子也只能二选一。这个问题其实可以直接从第一个问题升华。我们可以把这个问题直接拆解为选择第一个房子而忽略最后一个房子可以获得的最大收入，以及选择最后一个房子而忽略第一个房子可以获得的最大收入。
至于如果最好的情况是二者都不选的话，那么前一类和后一类都会覆盖这种情况，所以说这种分类可以覆盖全部的情况。
代码如下：
    public int rob(int[] nums) {
        if(nums==null || nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        return Math.max(rob(nums, 0, nums.length-2),rob(nums, 1, nums.length-1));
    }
    
    public int rob(int[] nums, int low, int high){
        int rob = 0;
        int notRob = 0;
        while(low<=high){
            int temp = rob;
            rob = notRob + nums[low];
            notRob = Math.max(temp, notRob);
            low++;
        }
        return Math.max(rob, notRob);
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU服务器海外云主机 Robber 198cdn House boston_housing

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70899.html

leetcode 198 House Robber

摘要：但是任何临近的两个房子被偷就会触发警报。要求我们求出在不触发警报的情况下偷到的最多的钱。每个房子里的钱通过输入的数组表示。题目详情 You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only...

jzman 2019-08-16 11:06 评论0 收藏0
[LeetCode] House Robber I II

摘要：注意对边界条件的判断，是否非空，是否长度为 House Robber I Problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping y...

qpal 2019-08-14 15:17 评论0 收藏0
[Leetcode] House Robber 打家劫舍

摘要：动态规划复杂度时间空间思路一般来说，给定一个规则，让我们求任意状态下的解，都是用动态规划。另外我们可以做一点优化，本来我们是要用一个数组来保存之前的结果的。所以我们分别算出这两个条件下的最大收益，然后取更大的就行了。可以复用的代码。 House Robber I You are a professional robber planning to rob houses along a ...

golden_hamster 2019-08-14 12:38 评论0 收藏0
LeetCode[337] House Robber III

摘要：复杂度思路对于每一个位置来说，考虑两种情况分别对和再进行计算。用对已经计算过的进行保留，避免重复计算。 LeetCode[337] House Robber III The thief has found himself a new place for his thievery again. There is only one entrance to this area, calle...

Dr_Noooo 2019-08-14 15:00 评论0 收藏0
[LintCode/LeetCode] House Robber II

摘要：因为取了队首就不能取队尾，所以对数组循环两次，一个从取到，一个从取到，比较两次循环后队尾元素，取较大者。注意，要先讨论当原数组位数小于时的情况。 Problem After robbing those houses on that street, the thief has found himself a new place for his thievery so that he wi...

OnlyLing 2019-08-14 15:34 评论0 收藏0