这是最简单的 DP，要么不偷当前家（得到的收益和上一家相同），要么偷取当前家（得到的收益等于上上家的收益加上当前家的收益），看谁更大，决定偷不偷。递推公式如下：
1
| dp[i]=max(dp[i-1],dp[i-2]+nums[i])
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0) return 0;
vector<int> dp(nums.size());
dp[0]=nums[0];
for(int i=1;i<nums.size();i++){
dp[i]=max(dp[i-1],(i>=2?dp[i-2]:0)+nums[i]);
}
return dp[nums.size()-1];
}
};
|