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.