198. House Robber

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int rob(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    if (nums.size() == 1) return nums[0];
    if (nums.size() == 2) return max(nums[0], nums[1]);
    int len = nums.size();
    vector<int> nums_tmp1(nums.begin(),nums.begin() + len-1);
    vector<int> nums_tmp2(nums.begin(),nums.begin() + len-2);
    return max(nums[len-1] + rob(nums_tmp2), rob(nums_tmp1));
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int rob(vector<int>& nums) {
    int len = nums.size();
    if (len == 0) return 0;
    if (len == 1)return nums[0];
    int* ans;
    ans = new int[len];
    ans[0] = nums[0];
    ans[1] = max(nums[0], nums[1]);
    for (int i = 2; i < len; i++) {
        ans[i] = max(nums[i] + ans[i - 2], ans[i - 1]);
    }
    return ans[len-1];
    delete []ans;
}

int main() {
    vector<int> a = { 2,7,9,3,1 };
    cout << rob(a) << endl;
    return 0;
}