这道题在House Robber的基础上，添加了最后一家和第一家也不能一起偷，所以要么偷第一家，要么偷最后一家，就需要进行两次 DP。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0) return 0;
if(nums.size()==1) return nums[0];
vector<int> dp(nums.size());
dp[0]=nums[0];
for(int i=1;i<nums.size()-1;i++){
dp[i]=max(dp[i-1],(i>=2?dp[i-2]:0)+nums[i]);
}
int max1=dp[nums.size()-2];
dp[0]=0;
for(int i=1;i<nums.size();i++){
dp[i]=max(dp[i-1],(i>=2?dp[i-2]:0)+nums[i]);
}
return max(max1,dp[nums.size()-1]);
}
};
|