house-robber.md

House Robber

Transitions

1. Robber chooses to rob the current house
2. Robber does not rob the current house

Top-down

The naive top-down approach would be trying all possibilities given the transitions:

def house_robber(houses):
    def rob(i):
        if i >= len(houses):
            return 0
        return max(rob(i + 1), rob(i + 2) + houses[i])
    return rob(0)

If house i isn't robbed, then we can move on to house i + 1 to try again.

If house i is robbed, then we can only start robbing from house i + 2 onwards.

This generates the following recurrence relation:

$$ dp(i) = \begin{cases} 0, i >= |houses|\\ \max(dp(i+1), dp(i+2)+houses[i]) \end{cases} $$

Deriving bottom-up

We will apply the trick of "re-framing the problem" to derive a bottom-up solution. Given a prefix of $$i-1$$ houses, can the optimal answer for house i be derived?

To rob house i, we must do so when we had not robbed the previous house, thus, we must have robbed at most house i - 2.

If house i is not going to be robbed, then the most amount of money we can rob from house 0 to i is the same as if we only looked out houses 0 to i - 1.

As a result, we can form a new recurrence relation:

$$ dp(i) = \begin{cases} houses[0], i =0\\ \max(houses[0], houses[1]), i = 1\\ \max(dp(i-1), dp(i-2)+houses[i]) \end{cases} $$

The base cases arise from the following observations:

1. If you only have 1 house, the optimal choice is always to rob it
2. If you have 2 houses, you can either rob the first but not the second or rob the second but not the first so we pick the maximum of the two

Bottom-up

We will apply the $$n$$ state caching optimization where $$n = 2$$.

def house_robber(houses):
    if len(houses) == 1: return houses[0]
    h1, h2 = houses[0], max(houses[0], houses[1])
    for i in range(2, len(houses)):
        h1, h2 = h2, max(h2, h1 + houses[i])
    return h2

Note that h1 corresponds to dp(i-2) and h2 corresponds to dp(i-1).