我好菜
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int rob(vector<int>& nums) {
int sz = nums.size();
if(sz == 1)
return nums[0];
if(sz < 3)
return max(nums[0], nums[1]);
int dpNotRobFirst[2];
int dpRobFirst[2];
dpNotRobFirst[0] = nums[1];
dpNotRobFirst[1] = max(nums[1], nums[2]);
dpRobFirst[0] = nums[0];
dpRobFirst[1] = max(nums[0], nums[1]);
for(int i = 2; i < sz - 1; ++i)
{
dpNotRobFirst[0] = max(dpNotRobFirst[1], dpNotRobFirst[0] + nums[i + 1]);
dpRobFirst[0] = max(dpRobFirst[1], dpRobFirst[0] + nums[i]);
swap(dpNotRobFirst[0], dpNotRobFirst[1]);
swap(dpRobFirst[0], dpRobFirst[1]);
}
return max(dpNotRobFirst[1], dpRobFirst[1]);
}
};
|
分为rob第一个和不rob第一个，问题变为rob[1, n - 2]和rob[2, n - 1]