你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報(bào)警。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動警報(bào)裝置的情況下，能夠偷竊到的最高金額。

示例 1:

輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。
示例 2:

輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。
偷竊到的最高金額 = 2 + 9 + 1 = 12 。

思路

當(dāng)只有兩個(gè)數(shù)，選擇數(shù)值最大，當(dāng)兩個(gè)數(shù)以上，dp[i]代表偷到第i家時(shí)金額最大，dp[i]的值需要將nums[i]與dp[i-2]相加，比較dp[i-1]，哪個(gè)大賦值給dp[i]

class Solution {
    public int rob(int[] nums) {
        
        int len=nums.length;
        if(len==0){
            return 0;
        }else if(len==1){
            return nums[0];
        }else if(len==2){
            if(nums[0]>nums[1]){
                return nums[0];
            }else{
                return nums[1];
            }
        }
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        if(nums[1]>nums[0]){
            dp[1]=nums[1];
        }else{
            dp[1]=nums[0];
        }
        
        for(int i=2;i<nums.length;++i){
            if(nums[i]+dp[i-2]>dp[i-1]){
                dp[i]=nums[i]+dp[i-2];
            }else{
                dp[i]=dp[i-1];
            }
           // dp[i]=nums[i]+dp[i-2]>dp[i-1]?nums[i]+dp[i-2]:dp[i-1];
        }
        return dp[nums.length-1];
    }
}