打家劫舍
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋槽驶。每間房內(nèi)都藏有一定的現(xiàn)金审洞，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入痕支，系統(tǒng)會自動報警乡摹。
給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組，計算你在不觸動警報裝置的情況下采转，能夠偷竊到的最高金額聪廉。
示例 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 干签。
動態(tài)規(guī)劃
分析
假設(shè)dp[ i ]為前 i 間房屋所能得到的最大利益津辩，那么dp[ i ]為以下兩種情況的最大值：1.第 i 間房屋不偷，則當(dāng)前最大利益為前 i - 1 間房的最大利益容劳，即dp[ i ] = dp[ i - 1 ]喘沿；2.第 i 間房屋偷，則當(dāng)前最大利益為前 i - 2 間房的最大利益加上第 i 間房的利益竭贩，即dp[ i ] = d[ i - 2 ] + nums[ i ]蚜印；（相鄰兩間房屋不能偷）
狀態(tài)轉(zhuǎn)移方程：dp[ i ] = max{ dp[ i - 1 ]，dp[ i - 2 ] + nums[ i ] }
class Solution {
public int rob(int[] nums) {
if(nums.length == 0)
return 0;
if(nums.length == 1)
return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for(int i = 2; i < nums.length; i++){
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}
模擬
分析
如果兩間相鄰的房屋在同一晚上被小偷闖入留量，系統(tǒng)會自動報警（即相鄰的數(shù)字不能同時作為最終求和的有效數(shù)字）窄赋。那么我們很容易聯(lián)想到求出奇數(shù)和以及偶數(shù)和，比較這兩個誰更大楼熄，誰就是最優(yōu)解忆绰。事實上還有一種情況可能出現(xiàn)最優(yōu)解，即部分是奇數(shù)和可岂，部分是偶數(shù)和错敢，例如[3,1,1,5,1,7,1]這樣的房屋排列，無論小偷偷奇數(shù)位置的房屋還是偶數(shù)位置的房屋都不能偷得最多的錢缕粹。所以我們在求和時還要將奇數(shù)和或偶數(shù)和更新為當(dāng)前最大和伐债，以至于當(dāng)前和總是處于最優(yōu)的狀態(tài)。最后返回兩個和中的最大值致开。
class Solution {
public int rob(int[] nums) {
int sumEven = 0;
int sumOdd = 0;
for(int i = 0; i < nums.length; i++){
if(i % 2 == 0){
sumEven += nums[i];
sumEven = Math.max(sumEven, sumOdd);
}else{
sumOdd += nums[i];
sumOdd = Math.max(sumEven, sumOdd);
}
}
return Math.max(sumEven, sumOdd);
}
}
