你是一個(gè)專業(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)裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。
示例 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 。
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400
正常動(dòng)態(tài)規(guī)劃做法，開一個(gè)一維的dp數(shù)組文章來源：http://www.zghlxwxcb.cn/news/detail-480374.html
class Solution {
public:
int rob(vector<int>& nums) {
int len=nums.size();
vector<int> dp(len+1);
if(len==1)
return nums[0];
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
for(int i=2;i<len;i++)
{
dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[len-1];
}
};省空間做法?？紤]到來到當(dāng)前的一個(gè)房屋所能偷到的最大金額只與前兩個(gè)房間有關(guān)，所以我們可以直接采取創(chuàng)建兩個(gè)變量來保存前兩個(gè)房間的信息，不斷更新即可。文章來源地址http://www.zghlxwxcb.cn/news/detail-480374.html
class Solution {
public:
int rob(vector<int>& nums) {
int len=nums.size();
if(len==1)
return nums[0];
int first=nums[0];
int second=max(nums[0],nums[1]);
for(int i=2;i<len;i++){
int temp=second;
second=max(nums[i]+first,second);
first=temp;
}
return second;
}
};到了這里，關(guān)于leetcode 打家劫舍（dp）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
