# LeetCode : 0198. House Robber (DP)
###### tags:`leetcode`
> C++ Vscode can be run

#include <bits/stdc++.h>

using namespace std;

class BaseSolution {
public:
    int rob(vector<int>& nums) {
        int robEven = 0, robOdd = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                robEven = max(robEven + nums[i], robOdd);
            } else {
                robOdd = max(robEven, robOdd + nums[i]);
            }
        }
        return max(robEven, robOdd);
    }
};

//don't combine house so divide Odd (1,3,5,7,9) Even (2,4,6,8,10)
//take easy Max (Odd Total money or Even Total money)

class Solution {
private:
    int n;
    vector<int> cache;
    const int INF = 987654321;
    int rob(vector<int>& nums, int index) {
        if (index == n) return 0;
        if (index > n) return -INF;
        
        int &ret = cache[index];
        if (ret != -1) return ret;
        
        int result = nums[index];
        result = max(result, nums[index] + rob(nums, index + 2));
        result = max(result, nums[index] + rob(nums, index + 3));
        return ret = result;
    }
    
public:
    int rob(vector<int>& nums) {
        n = nums.size();
        cache = vector<int>(n, -1);
        return max(rob(nums, 0), rob(nums, 1));
    }
};

class Solution2{
public:
    int rob(vector<int>& nums) {
        
        int n = nums.size(), pre = 0, cur = 0;
        for (int i = 0; i < n; i++) {
            //cout << "i = " << i << endl;
            //cout << "nums[" << i << "] = " << nums[i] << endl;
            int temp = max(pre + nums[i], cur);
            //cout << "temp =" << temp << endl;
            pre = cur;
            //cout << "pre = " << pre << endl;
            cur = temp;
            //cout << "cur = " << cur << endl;
        }
        return cur;
        //example: [5,7,9,3,8,2,9,4,3]
    }
};

int main(void)
{  
   //example: [5,7,9,3,8,2,9,4,3]
   Solution ROB;
   Solution2 ROB2;
      
   vector<int> intarr = {5,7,9,3,8,2,9,4,3};
   int ans = 0;
   //ans = ROB.rob(intarr);
   ans = ROB2.rob(intarr);

   cout << ans << endl;

   //cout << "test1\n";
   //printf("test\n");
   system("pause");
}

> Solution2
> Time complexity O(n)
> Space complexity O(1)