House Robber - Leetcode

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 1:

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.

Example 2:

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

 

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400a

Approach

This problem can not be solved by greedy approach.
Let us take an example:
nums = [1,7,9,5,1,3,4]

If we would go for max element in the array(ie. 9), we would loose its adjacent sum (ie. 7+5). And best we can have is 15 as total sum.

If we go for even or odd position elements we have even sum=15 (7+5+3) and odd sum=15(1+9+1+4).

The optimum answer for this example will be [7+5+4]=16.

Hence to solve this type of problem we have to search for all choices recursively and pick out the maximum from them. Let us denote that:

f(n) = Largest amount that you can rob from first house to nth indexed house.
Ai = Amount of money at the ith index house.

At each house we have the choice of robbing it or leaving it.
case 1 – if we pick last house:
then, we cant pick (n-1)th house, hence f(n)= An + f(n-2)
case 2 – if we leave last house:
then, we will stick with the max profit till (n-1)th house, hence f(n)= f(n-1)

Let us see base cases.
n = 0, clearly f(0) = A0.
n = 1, then f(1) = max(A0, A1).

Hence we can summarize the formula as following :
f(n)= max( An + f(n-2) , f(n-1) )

This is a recursive formula which we can implement through simple recursion but here the time complexity will be O(2^n). Therefore we will use dynamic programming approach and store the intermediate results in an array.
After calculating we will return the value stored at nth(last) index in array.

    //rob:   f(n) = A(n) + f(n-2)
    //leave: f(n) = f(n-1)

    public int rob(int[] nums) {
        int amt[] = new int[nums.length];
        
        if(nums.length==1)
            return nums[0];
        
        amt[0] = nums[0];
        amt[1] = Math.max(nums[0],nums[1]);
        
        
        for(int i=2;i<nums.length;i++){
            amt[i] = Math.max(nums[i]+amt[i-2],amt[i-1]);
        }
        
        return amt[nums.length-1];
    }