DP - 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 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.

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

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

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

Note that in the problem statement, it is said that if you rob house at index i, you have to skip house indexed at i+1, this doesn't mean that you have to rob the next house indexed at i+2. For instance look at example 3 above, to maximize the amount, we are skiping index 1 and 2 as well, and just taking 0 and 4 indxed houses.

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

In this approach, we will compute all possible combinations with conditions given in the problem, that is if we rob house at i, then we have to skip the adjascent indexed house i+1.

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.
- 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, we simply return 0.

public class HouseRobber { static int bruteForceApproach(int[] nums) { return bruteForceApproachRec(nums, 0); } static int bruteForceApproachRec(int[] nums, int start) { if(start>=nums.length) { return 0; } return Math.max(nums[start] + bruteForceApproachRec(nums, start+2), bruteForceApproachRec(nums, start+1)); } }

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.

If we look at the decision tree diagram from above brute force aproach, highlighted sub problems are overlapping.

If we look at the decision tree diagram from above brute force aproach, highlighted sub problems are overlapping.
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 HouseRobber { static int dpMemoizationApproach(int[] nums) { HashMap<Integer, Integer> cache = new HashMap<>(); return dpMemoizationApproachRec(nums, 0, cache); } static int dpMemoizationApproachRec(int[] nums, int start, HashMap<Integer, Integer> cache) { if(start>=nums.length) { return 0; } if(cache.containsKey(start)) { return cache.get(start); } int result = Math.max(nums[start] + bruteForceApproachRec(nums, start+2), bruteForceApproachRec(nums, start+1)); 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].

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. Lets look at an example with nums array as [1, 2, 3, 1].

In the first step, if the input array nums length is 1, just return the first element.
In the first step, we will be initializing dp array with same length as nums input array.
Then, update dp array with base cases. i.e. dp[0] = nums[0] and dp[1] = Max(nums[0], nums[1]), so the dp array looks like this after applying base cases. dp = [1, 2, 0, 0].
For the next index i=2, maximum amount you can rob at this index will be Max(nums[2] + dp[0], dp[1]) so the dp array now will be dp = [1, 2, 4, 0]
For the next index i=3, maximum amount you can rob at this index will be Max(nums[3] + dp[1], dp[2]) so the dp array now will be dp = [1, 2, 4, 4 ]
As you see, maximum amount is stored at last index, we can simply return that dp[dp.length-1].

public class HouseRobber { static int dpTabulationApproach(int[] nums) { if(nums.length == 1) { return nums[0]; } 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 Math.max(dp[dp.length-1], dp[dp.length-2]); } }

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.

public class HouseRobber { static int dpMemoryOptimized(int[] nums) { int m1= 0; int m2 = 0; for(int i=0; i<nums.length; 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: