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:

# want the larger one of these
NotBuy(n-1)   # max value if you don't buy the last house
Buy(n-1)      # max value if you buy 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:

NotBuy(i) = max(
    NotBuy(i-1), # come from NotBuy
    Buy(i-1)     # come from Buy
)

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:

Buy(i) = NotBuy(i-1) + prices[i]

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

NotBuy(i) = max(
    NotBuy(i-1),
    Buy(i-1)
)

Buy(i) = NotBuy(i-1) + prices[i]

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.

NotBuy(-1) = 0
Buy(-1) = -infinity

3. Code

We can code this up using "Tabulation+":

def richestLandlord(prices):
    # base case
    NotBuy = 0
    Buy = float('-inf')

    # recursion
    for i in range(len(prices)):
        Buy, NotBuy = NotBuy + prices[i], max(NotBuy, Buy)

    return max(Buy, NotBuy)

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.

# max value you can get if you consider buying houses 0...i (inclusive)
maxValue(i)

# recursion: either buy from the current house and keep value from the 2nd prev house, or don't buy the current house and keep value from the prev house
maxValue(i) = max(maxValue(i-2)+prices[i], maxValue(i-1))

maxValue(-1) = 0 # negative houses don't exist, so just set cost to 0
maxValue(0) = prices[0]

def richestLandlord(prices):
    # i = -1, 0
    Prev = 0
    Curr = prices[0]

    # i = 1, 2, ..., n-1
    for i in range(1, len(prices)):
        Curr, Prev = max(Prev+prices[i], Curr), Curr

    return max(Prev, Curr)