House Robber II

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. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, 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,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

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 house’s profit, if two houses, choose the largest profit.

3. Transition Function: This time we cannot simply do one iteration since we should consider that the last house’s profit. 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. And then, do another iteration counting the last house, simply starts from the fourth house (third house + 1) so that the last house will be taken into consideration. Therefore, it is a problem that does two iterations that counts either the first house or the last house and choose the one with the maximum profit.

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

The Code

class Solution {
    /*
        Dynamic Programming
        
        - This time we either choose the one with the first house or the one with the last house
        - Same solution
    */
    public int rob(int[] nums) {
        if(nums.length == 0 || nums == null){
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }
        if(nums.length == 2){
            return Math.max(nums[0], nums[1]);
        }
        
        // compare the profit with robbing the first house 
        // or the profit with robbing the last house
        int max_first = helper(nums, 0, nums.length - 1);
        int max_last = helper(nums, 1, nums.length);
        
        return Math.max(max_first, max_last);
    }
    
    public int helper(int[] nums, int i, int j){
        int[] dp = new int[nums.length];
        
        // base cases for [0] and [1]
        dp[i] = nums[i];
        dp[i+1] = Math.max(nums[i+1], nums[i]);
        
        for(int k = i + 2; k < j; k++){
            dp[k] = Math.max(dp[k-1], dp[k-2] + nums[k]);
        }
        
        return dp[j-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).