你是一個(gè)專(zhuān)業(yè)的小偷蹭睡，計(jì)劃偷竊沿街的房屋车海。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)涂邀，如果兩間相鄰的房屋在同一晚上被小偷闖入瘟仿，系統(tǒng)會(huì)自動(dòng)報(bào)警。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組比勉，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下劳较，能夠偷竊到的最高金額驹止。
示例 1:
輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號(hào)房屋 (金額 = 1) ，然后偷竊 3 號(hào)房屋 (金額 = 3)观蜗。
偷竊到的最高金額 = 1 + 3 = 4 臊恋。
示例 2:
輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號(hào)房屋 (金額 = 2), 偷竊 3 號(hào)房屋 (金額 = 9)，接著偷竊 5 號(hào)房屋 (金額 = 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];
}
}
