Today I worked on a LeetCode problem called House Robber: given an array of numbers, each representing the amount of money in the house, find the maximum amount of money you can rob without robbing neighboring houses.

Example:
Input: [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.

Here, it looks like one easy solution might be to simply get the sums of the values at alternating indices and choose the max of those:

max((1 + 3), (2 + 1))
// gives us 4

However, that doesn't work if the max can be the sum of non alternating values:
Input: [2,1,1,2]
Output: 4
Explanation: Rob house 1 ($2) and house 4 ($2) so 2 + 2 = 4

Observation: no matter the solution we're attempting, we can probably take care of some initial cases where the input length is small enough to be trivial.

if len(nums) == 0:
    return 0
if len(nums) == 1:
    return nums[0]
if len(nums) == 2:
    return max(nums[0], nums[1])

Observation: if we iterate through the array, we can save space and time complexity if we obtain the max value at the current index from the max values at the previous indices.

Maybe we can make the problem smaller by looking at the max values at i - 1 and i - 2, and creating a general rule from there. Often, people think of this kind of problem solving strategy recursively. Dynamic programming is an approach that is often an optimization of recursion because it involves storing the results of the smaller subproblems rather than creating a call stack and letting it bubble up.

Let's take the input of [2,7,9,3,1].
The max of the array [2] is 2.
The max of array [2,7] is 7.
The max of the array [2,7,9] is max(2 + 9, 7) = 11
The max of the array [2,7,9,3] is max(2 + 9, 7 + 3) = 11
The max of the array [2,7,9,3,1] is max (2 + 9 + 1, 7 + 3) = 12.

A pattern is emerging here: at each index, we keep checking if the current index added to each previous alternating index creates a new max value.

But there's repeated work! We keep adding 2 + 9 and 7 + 3. If the array were longer, we'd repeat this same work even more times.

What if we could keep a running tally of the max possible value at that index and just keep updating it as we go along? We actually need to keep track of two of these values because we can't rob neighboring houses. We can initialize these values like so:

max_one_back = max(nums[0], nums[1])
max_two_back = nums[0]

Now, if we start at the 3rd index in the array, we can check to see if adding the current number to the max_two_back will give us a bigger number than the max_one_back. If it does, we'll save it as the max value at the current index.

max_at_i = max(nums[i] + max_minus_two, max_minus_one)

After that, all we need to do is apply this strategy to the rest of the array and update the max variables as we go along. Here's the total solution I ended up with:

def rob(self, nums):
   if len(nums) == 0:
       return 0
   if len(nums) == 1:
       return nums[0]
   if len(nums) == 2:
       return max(nums[0], nums[1])
   
   max_minus_one = max(nums[0], nums[1])
   max_minus_two = nums[0]
   
   for i in range(2, len(nums)):
       max_at_i = max(nums[i] + max_minus_two, max_minus_one)
       
       max_minus_two = max_minus_one
       max_minus_one = max_at_i
       
   return max_at_i