This was a nice dynamic programming exercise, and part of the Leetcode-defined study guide. This is a fun alternative to the Dasgupta et. al. intro question of longest increasing subsequence. It feels like the same flavor. Perhaps a more peaceful formulation would be making it like choosing a sequence of moves in some game show, to win money.

The Core Approach

This is the first question in the sequence that really motivates, to my mind, a “real” dynamic programming formulation. In this case, we want a table T such that T[i] is the “best” thing for some category. To me the most interesting complication is how to express that choice implicitly in T. The counterintuitive trick I’ve learned is to have T involve committing to that choice.

Just as the Dasgupta LIS example has T[i] be the longest increasing subsequence ending at that point (so it’s committed to using the ith element as part of the sequence), we should have T[i] in this question be the most money you get if the last house you rob is house i.

On a more mechanical level, there are two harsh jumps in my mind:

1. We’re going from a linear algorithm to a quadratic algorithm. Not a problem, but as people seem to approach dynamic programming with some fearful awe, it may be worth to clear the way and say multiple scans over the table is OK.
2. The solution to the problem is not (necessarily) the last cell of the table. That is again fine, but again different from the previous questions.

The solution

No further ado, complete with unaltered comments to myself.

class Solution:
    def rob(self, nums: List[int]) -> int:
        T = []
        # T[i] = most money when comitting to robbing house at i
        # Observation: we encode the decision into our definition
        # of T, that's how we avoid having to think about more than
        # 1 house at a time (we instead look at the previous... 3 options?)
        # Interesting inputs: [10, 1, 1, 10], you don't want to rob either "1" house
        for i, v in enumerate(nums):
            options = T[:i-1] + [0]
            T.append(max(options)+nums[i])
        return max(T)