[Leetcode] House Robber 打家劫舍

golden_hamster 發(fā)布于2019-08-14 12:38 / 3480人閱讀

摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路一般來(lái)說(shuō)，給定一個(gè)規(guī)則，讓我們求任意狀態(tài)下的解，都是用動(dòng)態(tài)規(guī)劃。另外我們可以做一點(diǎn)優(yōu)化，本來(lái)我們是要用一個(gè)數(shù)組來(lái)保存之前的結(jié)果的。所以我們分別算出這兩個(gè)條件下的最大收益，然后取更大的就行了。可以復(fù)用的代碼。

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.

動(dòng)態(tài)規(guī)劃 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

一般來(lái)說(shuō)，給定一個(gè)規(guī)則，讓我們求任意狀態(tài)下的解，都是用動(dòng)態(tài)規(guī)劃。這里的規(guī)則是劫匪不能同時(shí)搶劫相鄰的屋子，即我們?cè)诶奂訒r(shí)，只有兩種選擇：

如果選擇了搶劫上一個(gè)屋子，那么就不能搶劫當(dāng)前的屋子，所以最大收益就是搶劫上一個(gè)屋子的收益

如果選擇搶劫當(dāng)前屋子，就不能搶劫上一個(gè)屋子，所以最大收益是到上一個(gè)屋子的上一個(gè)屋子為止的最大收益，加上當(dāng)前屋子里有的錢(qián)

所以，我們只要判斷一下兩個(gè)里面哪個(gè)大就行了，同時(shí)也是我們的遞推式。另外我們可以做一點(diǎn)優(yōu)化，本來(lái)我們是要用一個(gè)dp數(shù)組來(lái)保存之前的結(jié)果的。但實(shí)際上我們只需要上一次和上上次的結(jié)果，所以可以用兩個(gè)變量就行了。

代碼

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是當(dāng)前的最大受益
        int b = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++){
            int tmp = b;
            // 當(dāng)前的最大收益是兩種選擇里較大的那個(gè)
            b = Math.max(a + nums[i], b);
            a = tmp;
        }
        return b;
    }
}

House Robber II 動(dòng)態(tài)規(guī)劃 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

和I一樣，但是這里多了一條規(guī)則，抽象出來(lái)就是：搶劫第一個(gè)屋子就不能搶劫最后一個(gè)屋子，搶劫最后一個(gè)屋子就不能搶劫第一個(gè)屋子。所以我們分別算出這兩個(gè)條件下的最大收益，然后取更大的就行了。可以復(fù)用I的代碼。

代碼

public class Solution {
    
    public int rob(int[] nums) {
        // 求兩種條件下更大的那個(gè)，用一個(gè)offset表示是哪種條件
        return Math.max(rob(nums, 0), rob(nums, 1));
    }
    
    public int rob(int[] nums, int offset) {
        // 如果長(zhǎng)度過(guò)小，則直接返回結(jié)果
        if(nums.length <= 1 + offset){
            return nums.length <= offset ? 0 : nums[0 + offset]; 
        }
        int a = nums[0 + offset];
        // 如果offset是1，則從下標(biāo)為1的元素開(kāi)始計(jì)算，所以要比較nums[1]和nums[2]
        int b = Math.max(nums[0 + offset], nums[1 + offset]);
        // 對(duì)于不搶劫最后一個(gè)房子的情況，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;
    }
}