House Robber

Rob the most amount of money.

Question

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:

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.

Analyzation

1. This dp array is for calculating the maximum profit of a robber and it is a bottom-up(iterative) approach.

2. Initialization: If there is no house, return 0, if only one house, return that houses’ profit, if two houses, choose the largest profit.

3. Transition Function: Starting from the third house till the last house, the robber will choose either the current house and the house before the previous one, or the previous house, and calculate which one has the largest profit.

4. Result: return the last index of the house because it is a bottom-up approach.

The Code

class Solution {
    /*
        Dynamic Programming
    */
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        
        if(nums.length == 1){
            return nums[0];
        }
        
        if(nums.length == 2){
            return Math.max(nums[0], nums[1]);
        }
        
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        for(int i = 2; i < nums.length; i++){
            // we rob the current house or just rob the previous house
            dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
        }
        
        return dp[nums.length-1];
    }
}

Time & Space Complexity

• Time Complexity: Since we create a loop so it is O(n).
• Space Complexity: Since we create a dp array, the Space Complexity is O(n).