DAY 13 - House Robber

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-13.

DAY 13 Problem 1: House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Intuition:

Well This problem can seem pretty tricky at first. One might even think of using greedy in this case as it requires us to maximize our profit. But greedy focuses on the local optimum solution and hence misses the mark here. We will have to use DP here.

Approach:

The way to look at this problem is in a recursive way.
Just like we did in combination sum, we have to options:
Either to rob the house/include the house in our profits or not include the house.
We will follow that approach and reduce down its complexity using tabulation Dynamic Programming.

Code:

int solve(vector<int> &nums)
    {int n = nums.size();
        vector<int> dp(n+1,0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i = 1; i < n; i++)
        {
            int incl = dp[i-2] + nums[i];
            int excl = dp[i-1];
            dp[i] = max(incl, excl);
        }
        return dp[n-1];

    }
    int rob(vector<int>& nums) {
        return solve(nums);

    }

Complexity Analysis:

Time Complexity: O(N)
Space Complexity: O(N)

We can further reduce the space complexity. If we look closely, the indexes dp[i],dp[i-1] and dp[i-2] are just changing their positions relative to each other.
Hence we don't need to maintain a full array count but rather two pointers for this.

Code:

int solve(vector<int> &nums)
    {int n = nums.size();
        vector<int> dp(n+1,0);
        int prev2 = 0;
        int prev = nums[0];

        for(int i = 1; i < n; i++)
        {
            int incl = prev2+ nums[i];
            int excl = prev;
            int ans = max(incl, excl);
            prev2 = prev;
            prev = ans;
        }
        return prev;

    }
int rob(vector<int> &nums){
    return solve(nums);
}

Complexity Analysis:

Time Complexity: O(N)
Space Complexity: O(1)