Leetcode 198. House Robber

Problem Link https://leetcode.com/problems/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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [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.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

Solution:
We are given integers representing the amount of money at ith house. Our task is to maximize the total money. The constraint is that we are not allowed to rob two consecutive houses.
Let's say we rob 0th house then we can't rob 1st house.

I'll be solving this problem using bottom-up dp.
Suppose dp[i] is the total maximum amount of money that we can rob till ith house.
Clearly:

 dp[0] = nums[0] 

as the total amount of money, we can rob till house 0 is what is in house 0 itself. Also, we can see that the total maximum amount we can rob till house 1st is

 dp[1] = max(nums[0], nums[1]) 

which means we rob either of the house 0 or 1 which has the maxim value.


For all other houses i , we can have maximum  if we don't rob the current house and rob (i - 1)th house or rob ith house with value nums[i]

 dp[i] = max(dp[i - 1], nums[i] +  dp[i - 2]); 

Implementation:

class Solution {
public:
    int rob(vector& nums) {
        // If there is no house
        //  Maximum sum that we can rob is 0
        if(nums.size() == 0){
            return 0;
        }
        
        // If there is only 1 house maximum money is \
        // by robbing the only house
        if(nums.size() == 1){
            return nums[0];
        }
        
        // If there are 2 houses we can rob one of the houses
        // But not both of them as they are consecutive
        // So we maximize the robbery by chossing the house with maximum value
        if(nums.size() == 2){
            return max(nums[0], nums[1]);
        }
        
        // dp[i] stores the maximum value that we can rob till ith house
        vector dp(nums.size(), 0);
        
        // Base Cases
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        // For all houses from i = 2 to n - 1
        // Either rob the ith house giving maxm value = nums[i] + dp[i - 2]
        // Or dont rob ith house by giving maximum vale = d[i - 1]
        // We choose the maximum of these two values
        for(int i = 2; i < nums.size(); i++){
            dp[i] = max(dp[i - 1], nums[i] +  dp[i - 2]);
        }
        
        // return maximum value we can rob till (n - 1)th house
        return dp[nums.size() - 1];
    }
};