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.
Credits:Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.
Subscribe to see which companies asked this question.

題目

假設(shè)你是一個(gè)專業(yè)的竊賊素挽，準(zhǔn)備沿著一條街打劫房屋填帽。每個(gè)房子都存放著特定金額的錢秉撇。你面臨的唯一約束條件是：相鄰的房子裝著相互聯(lián)系的防盜系統(tǒng)床未，且 當(dāng)相鄰的兩個(gè)房子同一天被打劫時(shí)，該系統(tǒng)會(huì)自動(dòng)報(bào)警清钥。
給定一個(gè)非負(fù)整數(shù)列表州叠，表示每個(gè)房子中存放的錢， 算一算浩聋，如果今晚去打劫观蜗，你最多可以得到多少錢 在不觸動(dòng)報(bào)警裝置的情況下。
樣例
給定 [3, 8, 4], 返回 8.

分析

動(dòng)態(tài)規(guī)劃解決衣洁。
dp[i]:打劫前i個(gè)房子最多可以得到的錢
遇到第i個(gè)房子墓捻，兩種選擇打劫或者不打劫，所以
狀態(tài)轉(zhuǎn)移方程：
dp[i] = Max(dp[i-1],res[i-2]+A[i-1])
初始條件：
dp[0]= 0
dp[1] = A[0]

代碼

public class Solution {
    /**
     * @param A: An array of non-negative integers.
     * return: The maximum amount of money you can rob tonight
     */
    //---方法一---
    public long houseRobber(int[] A) {
        // write your code here
        int n = A.length;
        if(n == 0)
            return 0;
        long []res = new long[n+1];
        
        
        res[0] = 0;
        res[1] = A[0];
        for(int i = 2; i <= n; i++) {
            res[i] = Math.max(res[i-1], res[i-2] + A[i-1]);
        }
        return res[n];
    }
    //---方法二---
    public long houseRobber(int[] A) {
        // write your code here
        int n = A.length;
        if(n == 0)
            return 0;
        long []res = new long[2];
        
        
        res[0] = 0;
        res[1] = A[0];
        for(int i = 2; i <= n; i++) {
            res[i%2] = Math.max(res[(i-1)%2], res[(i-2)%2] + A[i-1]);
        }
        return res[n%2];
    }
}

Paste_Image.png

方法二

同樣的是動(dòng)態(tài)規(guī)劃坊夫，由于每個(gè)點(diǎn)只存在兩個(gè)狀態(tài)砖第，即打劫或者不打劫，所以我們可以使用一個(gè)變量來(lái)保存這個(gè)狀態(tài)环凿，所以利用一個(gè)二維數(shù)組
dp[i][0]:表示不打劫第i個(gè)房屋的最大價(jià)值
dp[i][1]:表示打劫第i個(gè)房屋的最大價(jià)值

public class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0)
                return 0;
            int[][] dp = new int[nums.length+1][2];
            
            for(int i=1;i<=nums.length;i++) {
                dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
                dp[i][1] = nums[i-1] + dp[i-1][0];
            }
            
            return Math.max(dp[nums.length][0], dp[nums.length][1]);
    }
}

Paste_Image.png