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 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.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

這道題的本質(zhì)相當(dāng)于在一列數(shù)組中取出一個或多個不相鄰數(shù)蔑穴，使其和最大聊浅。

遞歸思路

從第 0 家開始偷，假設(shè)第 0 家偷封救，因?yàn)椴荒芡迪噜彽奶汛埽敲聪麓尉褪菑?[2,n] 開始圣勒，如果第 0 家不偷膝迎，那么下次就是從 [1,n] 開始偷。一直遞歸直到最后一家灰蛙。

解法1：暴力枚舉

class Solution {
    public int rob(int[] nums) {
        return rob(0,nums);
    }
    //1祟剔、思考遞歸退出的邊界條件
    //2、寫遞歸過程
    //3摩梧、返回結(jié)果
    public int rob(int idx,int[] nums) {
        if(idx >= nums.length){
            return 0;
        }
       int a = nums[idx] + rob(idx+2,nums);//假設(shè)第一家偷物延，那下一家就是 idx+2，進(jìn)行遞歸
        int b = 0 + rob(idx+1,nums);//第一家不偷仅父，則為0叛薯，下一家就是 idx+1，再進(jìn)行遞歸
        int c = Math.max(a,b);
        return c;
    }
}

解法2：加緩存

暴力枚舉在 Leetcode 會超時笙纤，而在上面的遞歸樹中耗溜，有很多重復(fù)遞歸遍歷的節(jié)點(diǎn)，這里就需要增加緩存粪糙，如果已經(jīng)遍歷過强霎，就直接返回。

class Solution {
    private Map<Integer,Integer> cache = new HashMap<>();
    public int rob(int[] nums) {
        cache.clear();//緩存之前先清理緩存
        return rob(idx,nums);
    }
    //1蓉冈、思考遞歸退出的邊界條件
    //2、緩存判斷在邊界條件后執(zhí)行
    //3轩触、寫遞歸過程
    //4寞酿、在返回結(jié)果的地方進(jìn)行緩存
    //5、返回結(jié)果
    public int rob(int idx,int[] nums) {
        if(idx >= nums.length){
            return 0;
        }
        if(cache.containsKey(idx)) {
            return cache.get(idx);
        }
        int a = nums[idx] + rob(idx+2,nums);
        int b = 0 + rob(idx+1,nums);
        int c = Math.max(a,b);
        cache.put(idx,c);
        return c;
    }
}

解法3：循環(huán)變量

class Solution {
    public int rob(int[] nums) {
        return robot(nums);
    }
    //1脱柱、思考遞歸退出的邊界條件
    //2伐弹、緩存判斷在邊界條件后執(zhí)行
    //3、寫遞歸過程
    //4榨为、在返回結(jié)果的地方進(jìn)行緩存
    //5惨好、返回結(jié)果
    
    //Map緩存
    private Map<Integer,Integer> cache = new HashMap<>();
    public int robot(int[] nums) {
        if(nums==null || nums.length==0){
            return 0;
        }
        if(nums.length == 1) return nums[0];
        //清緩存
        cache.clear();
        int n = nums.length;
        //遞歸自下而上進(jìn)行煌茴，從第 n 家開始偷，直到第一家為止
        //對比上面的遞歸算法日川，寫出循環(huán)就比較簡單
        cache.put(n-1,nums[n-1]);
        cache.put(n-2,Math.max(nums[n-1],nums[n-2]));
        for(int i=n-3; i>=0; --i){
            cache.put(i,Math.max(nums[i] + cache.get(i+2), cache.get(i+1)));
        }
        return cache.get(0);
    }
    
    //數(shù)組緩存
    private int[] caches = new int[10000];
    public int robot1(int[] nums) {
        if(nums==null || nums.length==0){
            return 0;
        }
        if(nums.length == 1) return nums[0];
        int n = nums.length;
        caches[n-1] = nums[n-1];
        caches[n-2] = Math.max(nums[n-1],nums[n-2]);
        for(int i=n-3; i>=0; --i){
            caches[i] = Math.max(nums[i] + caches[i+2], caches[i+1]);
        }
        return caches[0];
    }
}

DP 解題步驟

1. 設(shè)計(jì)暴力算法蔓腐，找到冗余
2. 設(shè)計(jì)并存儲狀態(tài)（一維，二維龄句，三維數(shù)組回论，甚至Map）
3. 遞歸式（狀態(tài)轉(zhuǎn)移方程）
4. 自底向下計(jì)算最優(yōu)解（編程方式）