class Solution {
int dp[2][1005];
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 1) return nums[0];
// don't rob it
int ret = robUtil(vector<int>(nums.begin()+1, nums.end()));
// rob it
if(nums.size() > 3) ret = max(ret, robUtil(vector<int>(nums.begin() + 2, prev(nums.end()))) + nums[0]);
else {
ret = max(ret, nums[0]);
}
return ret;
}
int robUtil(vector<int> nums) {
int ret = 0;
int n = nums.size();
vector<vector<int>> dp(2, vector<int>(n));
dp[1][0] = nums[0];
for(int i = 1; i < n; ++i) {
dp[0][i] = max(dp[0][i-1], dp[1][i-1]);
dp[1][i] = dp[0][i-1] + nums[i];
}
return max(dp[0][n-1], dp[1][n-1]);
}
};
// the 0th is robbed, the 0th is robbed
// dp[0][i]: the maximum gain after robbing until the i-th house, the i-th house not robbed
// dp[1][i]: the maximum gain after robbing until the i-th house, the i-th house robbed
// [1] 0 [x x x x] 0
// [0] [x x x x ]
