# House Robber

Last updated

Last updated

Transitions

Robber chooses to rob the current house

Robber does not rob the current house

Top-down

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

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

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:

The base cases arise from the following observations:

If you only have 1 house, the optimal choice is always to rob it

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

Note that `h1`

corresponds to `dp(i-2)`

and `h2`

corresponds to `dp(i-1)`

.

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?

$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}$

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