[LeetCode] House Robber

The first version:

class Solution {  
public:  
    int rob(vector<int>& nums) {
        switch(nums.size()) {
        case 0:
            return 0;
        case 1:
            return nums[0];
        case 2:
            return max(nums[0], nums[1]);
        }

        int *dp = new int[nums.size() + 1];
        dp[0] = 0;
        dp[1] = nums[0];

        for(int i = 2; i <= nums.size(); i++) {
            dp[i] = max(nums[i - 1] + dp[i - 2], dp[i - 1]);
        }

        int result = dp[nums.size()];
        delete[] dp;

        return result;
    }
};

We noticed that only the message of dp[i-1] and dp[i-2] is used, so we can improve this.

Second version:

class Solution {  
public:  
    int rob(vector<int>& nums) {
        switch(nums.size()) {
        case 0:
            return 0;
        case 1:
            return nums[0];
        }

        int dp_0 = nums[0];
        int dp_1 = 0;
        int dp_2 = 0;
        int tmp;

        for(int i = 1; i < nums.size(); i++) {
            dp_2 = dp_1;
            dp_1 = dp_0;

            dp_0 = max(nums[i] + dp_2, dp_1);
        }

        return dp_0;
    }
};

It's also very slow now.I wonder how to optimize it.