DP - House Robber II

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 a security system 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.

Input: nums = [2, 3, 2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and house 3 (money = 2) as these two are adjascent.
So, the total amount will be 3.

Input: nums = [1, 2, 3, 1]
Output: 4
Explanation: You can rob house 1 (money = 1), house 3 (money = 3).
So, the total amount will be 4

Input: nums = [1, 2, 3]
Output: 3
Explanation: You can rob house 3 (money = 3)
So, the total amount will be 3

This problem is similar to House Robber problem, but with a small logic change, that is if you choose to rob 1 If you haven't looked into that problem, check it because it will give you foudation logic for the current problem.

Solution intution from previous house robber problem
Solution 1 - using brute force approach
Solution 2 - using DP memoization
Solution 3 - using DP Bottom-Up approach using tabulation
Solution 4 - using DP Bottom-Up approach memory optimized

This problem is a similar to the previous HouseRobber problem, only difference is if you choose to rob 1^st house, then you cannot rob the last house and vice versa, this is because all houses are in circle shape, so first and last houses are adjacent to each other. To solve this problem, what we are going to do is that apply previous house robber solution two times.

First time using houses from 1,......n-1, i.e. excluding last house, this way if you consider 1^st house then you are ignoring last house since they are adjascent to each other.
Second time using houses from 2,.....n, i.e. excluding first house, this way you are considering last indexed house, but ignoring the first house since they are adjascent to each other.

Then, finally take the maximum from these two results.

In this approach, we will apply the solution intution discussed above to the brute force approach, that is to compute all possible combinations with conditions given in the problem, we will run this process on sub arrays 0...n-1 and 1....n and then take maximum from these two outcomes.

We will create a function bruteForceApproach that takes nums array as input argument.
Create another helper function bruteForceApproachRec that take nums and start variable to indicate the start index of the sub array we should be considering and end variable to indicate the end index of sub array we should be considering.
- Call this function recursively, by moving start to +2 index considering you want to rob current house and +1 index considering you dont want to rob the current house, and take the maximum out of these two possibilities.
- Base case will be, when it reaches end of array or goes out of bounds as we are trying with +1 and +2 index from every start index, and when start index becomes greater than end index, then we simply return 0.
Call bruteForceApproachRec two times. First, with start =0, end = nums.length-2, i.e. ignoring last indexed house since we are considering first house. Second, with start =1, end = nums.length--1, i.e. ignoring first indexed house since we are considering last house.

public class HouseRobber2 { /* brute force approach*/ static int bruteForceApproach(int[] nums) { int one = bruteForceApproachRec(nums, 0, nums.length-2); int two = bruteForceApproachRec(nums, 1, nums.length-1); return Math.max(one, two); } static int bruteForceApproachRec(int[] nums, int start, int end) { if(start>=nums.length) { return 0; } if(start > end) { return 0; } return Math.max(nums[start] + bruteForceApproachRec(nums, start+2, end), bruteForceApproachRec(nums, start+1, end)); } }

Complexity Analysis:

Time complexity: Above code runs in O(2ⁿ) time where n is the length of nums input array, this is because we are creating a decision tree with two possibilities at each step.
Space complexity: O(n) as we are making recursive loops n times and this is the memory used by stack.

From the above brute force approach, we can notice that there are some overlapping problems.

So, in this approach, we will be caching sub problem result into a HashMap with start index as key and its result as value. When a sub problem is repeated and found in cache, we will return it, otherwise we will call the function recursively and cache its result.

import java.util.HashMap; public class HouseRobber2 { /* DP memoization*/ static int dpMemoizationApproach(int[] nums) { HashMap<Integer, Integer> cache = new HashMap<>(); int one = dpMemoizationApproachRec(nums, 0, nums.length-2, cache); int two = dpMemoizationApproachRec(nums, 1, nums.length-1, cache); return Math.max(one, two); } static int dpMemoizationApproachRec(int[] nums, int start, int end, HashMap<Integer, Integer> cache) { if(start>=nums.length) { return 0; } if(start > end) { return 0; } if(cache.containsKey(start)) { return cache.get(start); } int result = Math.max(nums[start] + bruteForceApproachRec(nums, start+2, end), bruteForceApproachRec(nums, start+1, end)); cache.put(start, result); return result; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums input array.
Space complexity: O(n) for the cache we are maintaining and stack for recursive calls.

In this approach we will look at solving the problem using Dynamic programming using tabulation caching mechanism.
The time and memory complexity will be same as above solution using memoization, but we can notice a pattern to improve memory complexity to constant in later solution.

Intution behind this solution is, when we are at i^th indexed house, we will calculate the maximum amount that can be robbed at this index and cache that into dp temporary array. We gonna compute maximum amount that you can rob using below logic. Max(nums[i] + dp[i-2], dp[i-1]) So, at every index, if you are robbing current indexed house then you can also add i-2 value to it, adding dp[i-2] or if you choose not to rob current indexed house, then take previous index value dp[i-1].

We will repeat this solution for house indexed 0....n-1 and 1......n, since the first house and last house are adjascent to each other. Finally take maximum from these two.

Base cases for this solution will be

dp[0] = nums[0], because at 0^th index, maximum amount you can rob is just that house.
dp[1] = Max(nums[0], nums[1]), because at 0^th indexed house has higher amount, you can rob that house and skip index 1 house or rob index 1 house and skip index 0 house.

Finally, take the last element from dp array, that will store the maximum amount that you can rob with the given conditions.

Since we need to call this for houses indexed 0.....n-1 and 1.....n, we will take the maximum out of these two results.

public class HouseRobber2 { /* DP tabulation approach */ static int dpTabulationApproach(int[] nums) { int[] excl_last_house = new int[nums.length -1]; System.arraycopy(nums, 0, excl_last_house,0,nums.length-1); int max1 = dpTabulationApproachHelper(excl_last_house); int[] excl_first_house = new int[nums.length-1]; System.arraycopy(nums,1,excl_first_house,0, nums.length-1); int max2 = dpTabulationApproachHelper(excl_first_house); return Math.max(max1, max2); } static int dpTabulationApproachHelper(int[] nums) { 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++) { dp[i] = Math.max(nums[i]+dp[i-2], dp[i-1]); } return dp[dp.length-1]; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums input array.
Space complexity: O(n) since we have a dp array with size n.

If we look at above DP solution using tabulation, when calculating maximum amount you can rob at index i, we just need previous two values, that is maximum amount you can rob at i-2 and i-1.

In this approach, we will create two variables m1 and m2 to hold previous values for i-2^nd step and i-1^st indexed houses.
We will initialize m1 = 0 and m1 = 0.
Next, for each index i compute the maximum that can be robbed using Max(nums[i]+m1, m2), store this into a temporary variable, then make this value as new m2 and current m2 to m1 for next iteration.

Since we need to call this for houses indexed 0.....n-1 and 1.....n, we will take the maximum out of these two results.

public class HouseRobber2 { /* DP optimized */ static int dpOptimized(int[] nums) { int max1 = dpOptimizedHelper(nums, 0, nums.length-2); // excluding the last house int max2 = dpOptimizedHelper(nums, 1, nums.length-1); // excluding the first house return Math.max(max1, max2); } static int dpOptimizedHelper(int[] nums, int start, int end) { int m1 = 0; int m2 = 0; for(int i=start;i<=end; i++) { int temp = Math.max(nums[i]+m1, m2); m1 = m2; m2 = temp; } return m2; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums input array.
Space complexity: O(1) since we are only using m1, m2 and a temp variables.

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis:

Complexity Analysis:

Complexity Analysis:

Complexity Analysis: