題目描述
你是一個專業(yè)的小偷视搏，計劃偷竊沿街的房屋漫仆。每間房內(nèi)都藏有一定的現(xiàn)金掸宛，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入肴焊，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組功戚，計算你 不觸動警報裝置的情況下 娶眷，一夜之內(nèi)能夠偷竊到的最高金額。
示例 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 。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 400
解題思路
- 動態(tài)規(guī)劃
記dp[i]為前i家偷竊到的最高金額灯萍，那么有：
dp[i]=max(dp[i-2]+nums[i],dp[i-1])
考慮臨界條件轧铁，數(shù)組長度為0，返回0旦棉；為1属桦，返回返回nums[0]；為2他爸，返回max(nums[0],nums[1])，其余返回dp[n-1]果善。
源碼
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0)
{
return 0;
}
else if(nums.size()==1)
{
return nums[0];
}
int n=nums.size();
vector<int> dp(n);
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
for(int i=2;i<n;i++)
{
dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[n-1];
/*
// 空間復(fù)雜度優(yōu)化
int pre_pre=nums[0];
int pre=max(nums[0],nums[1]);
for(int i=2;i<n;i++)
{
int cur=max(pre,pre_pre+nums[i]);
pre_pre=pre;
pre=cur;
}
return pre;
*/
}
};
題目來源
來源：力扣（LeetCode）
