Recursion

Richest Landlord

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:

prices = [3, 3, 3]=> returns 6\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)O(n). We iterate through every num in prices once.

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

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

Mark as Completed:
Submits:
richestLandlord
Test your code to get an output here!
richestLandlord(
)
Test your code to get an output here!