Recursion

You're a landlord, and you want to buy the most valuable houses in a neighborhood. Due to regulations, you're not allowed to buy 2 houses that are next to each other. All the houses are on a single, straight road.

You're given the price of each house `prices`

. Return the maximum value of houses that you can buy.

**Example:**

$\notag
\large \texttt{prices = [3, 3, 3]}\\
\large \texttt{=> returns 6}$

**Explanation:**
You can buy the first and last house, with a total value of 3+3=6.

First Few Test Cases:

0. Problem

We can describe this problem by saying you're in one of two states: the "Buy" state, where you bought the current house, or the "Not Buy" state where you didn't. The actions you're allowed to take are based on which state you're in - if you bought the current house, you're not allowed to buy the next house.

Here's a picture that describes this. The dots represent the state we're in, and the arrows represent the actions we can take (buy or not buy):

You're not allowed to buy two houses in a row, so there are no arrows that go between one Buy state and another Buy state.

We're looking for the max value when you're done with the last house:

1. Recursion

To get the recursion for the NotBuy state, we can look at the arrows that point to it:

We can follow the arrow from the previous Buy state, in which case we bought a total value of `NotBuy(i-1)`

. We can also follow the arrow from the previous Buy state, in which case we bought a total value of `Buy(i-1)`

.

We can take the max over these two options to find the maximum value we can make in the NotBuy state:

We can use the same logic to write the recursion for the Buy state:

We can follow the arrow from the NotBuy to the Buy state. In this case, we've bought a total value of `NotBuy(i-1)`

, and we also spend money `prices[i]`

to buy the current house. Here's the recursion for this:

We're done finding the recursion for this problem. Here are our results:

2. Base case

The recursion calls itself on smaller and smaller inputs. Eventually, it gets to the very first day `NotBuy(-1)`

and `Buy(-1)`

, which should be the base cases.

On the first day, you spent 0 dollars and haven't bought anything. This means that `NotBuy(-1) = 0`

. Also, we shouldn't even consider the buy state `Buy(-1)`

, because we haven't bought anything yet on that day. We can set its value equal to -infinity, since -infinity will always be ignored when we take a maximum.

3. Code

We can code this up using "Tabulation+":

Time Complexity $O(n)$. We iterate through every num in `prices`

once.

Space Complexity $O(1)$. We only use 2 variables.

For completeness, below is an alternative Dynamic Programming solution to the state-based one.

0. Problem

1. Recursion

2. Base case

The recursion depends on the values at the previous two houses, so we need two base cases.

3. Code

We can use "Tabulation+".

Time Complexity $O(n)$

Space Complexity $O(1)$

Mark as Completed: