[Leetcode] House Robber 打家劫舍

golden_hamster 发布于2019-08-14 12:38 / 3295人阅读

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

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.

动态规划 复杂度

时间 O(N) 空间 O(1)

思路

一般来说，给定一个规则，让我们求任意状态下的解，都是用动态规划。这里的规则是劫匪不能同时抢劫相邻的屋子，即我们在累加时，只有两种选择：

如果选择了抢劫上一个屋子，那么就不能抢劫当前的屋子，所以最大收益就是抢劫上一个屋子的收益

如果选择抢劫当前屋子，就不能抢劫上一个屋子，所以最大收益是到上一个屋子的上一个屋子为止的最大收益，加上当前屋子里有的钱

所以，我们只要判断一下两个里面哪个大就行了，同时也是我们的递推式。另外我们可以做一点优化，本来我们是要用一个dp数组来保存之前的结果的。但实际上我们只需要上一次和上上次的结果，所以可以用两个变量就行了。

代码

public class Solution {
    public int rob(int[] nums) {
        if(nums.length <= 1){
            return nums.length == 0 ? 0 : nums[0];
        }
        // a是上次的最大收益
        int a = nums[0];
        // b是当前的最大受益
        int b = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++){
            int tmp = b;
            // 当前的最大收益是两种选择里较大的那个
            b = Math.max(a + nums[i], b);
            a = tmp;
        }
        return b;
    }
}

House Robber II 动态规划 复杂度

时间 O(N) 空间 O(1)

思路

和I一样，但是这里多了一条规则，抽象出来就是：抢劫第一个屋子就不能抢劫最后一个屋子，抢劫最后一个屋子就不能抢劫第一个屋子。所以我们分别算出这两个条件下的最大收益，然后取更大的就行了。可以复用I的代码。

代码

public class Solution {
    
    public int rob(int[] nums) {
        // 求两种条件下更大的那个，用一个offset表示是哪种条件
        return Math.max(rob(nums, 0), rob(nums, 1));
    }
    
    public int rob(int[] nums, int offset) {
        // 如果长度过小，则直接返回结果
        if(nums.length <= 1 + offset){
            return nums.length <= offset ? 0 : nums[0 + offset]; 
        }
        int a = nums[0 + offset];
        // 如果offset是1，则从下标为1的元素开始计算，所以要比较nums[1]和nums[2]
        int b = Math.max(nums[0 + offset], nums[1 + offset]);
        // 对于不抢劫最后一个房子的情况，i要小于nums.length - 1
        for(int i = 2 + offset; i < nums.length - 1 + offset; i++){
            int tmp = b;
            b = Math.max(a + nums[i], b);
            a = tmp;
        }
        return b;
    }
}

云服务器专线服务 Robber House LeetCode LeetCode_String

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

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

LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
leetcode198,213 house robber

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

whidy 2019-08-16 11:01 评论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[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