Algorithms: Dynamic Programming, House Robber

Problem

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] <= 400

Solution

Get jesse kovash’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

At first glance, this seems very straightforward. Return the greater of the two sums: all odd-numbered houses, or all even-numbered houses. None of these problems are that straightforward so I thought of an edge case that would not pass this current logic.

For this test case, it is more advantageous to skip two houses in a row. It does not make sense to skip more than two houses since you would be unnecessarily skipping a house with adequate spacing.

It is possible to take a recursive approach for this problem, but the time limit will be exceeded on larger inputs.

1. Check if the input has available houses, if not return 0
2. Create an array to memoize our values as we iterate through the input. It should be the same length as the input
3. In this new array, load the zero index with the zero index value from nums, and set the first index of the new array equal to the value that is greater between the zero and first index of the input.
4. Since we filled in the first 2 values, we can start our iteration from index two. On each iteration we will need to assign the value of arr[i] to be the greater of two values: either the previous value arr[i-1] or arr[i-2] + nums[i]. This reassignment is allowing us to memoize the greater of the two options. This provides a significant time saving vs a recursive approach.
5. Our greatest sum will be the last value in arr.