[Leetcode] House Robber 打家劫舍

golden_hamster 發布于2019-08-14 12:38 / 3485人閱讀

摘要：動態規劃復雜度時間空間思路一般來說，給定一個規則，讓我們求任意狀態下的解，都是用動態規劃。另外我們可以做一點優化，本來我們是要用一個數組來保存之前的結果的。所以我們分別算出這兩個條件下的最大收益，然后取更大的就行了。可以復用的代碼。

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;
    }
}

云服務器 GPU云服務器 Robber House LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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