• 1 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 400
• Chosen houses must not be adjacent in the array
• The houses form a straight line, not a circle

You get to pick a set of houses. The only rule is that no two picked houses may sit side by side in the array. Your score is the sum of what you picked, and you want that score as large as possible.

Two things to be clear about before starting. Adjacent means adjacent in the array, so you can absolutely rob houses 0 and 2, or 0 and 5 — the gap does not need to be small, it just needs to exist. And the houses form a line, not a loop, so the first and last houses are not neighbours. If they were, this would be a genuinely harder problem.

Most people reach first for a simple rule. Every simple rule breaks, and it is worth seeing exactly how, because it explains why we need to do real work.

"Rob every other house." On [2, 1, 1, 2] that takes indices 0 and 2 for a total of 3. But 0 and 3 are not adjacent, and they give 4.

"Always grab the biggest remaining house, then cross out its neighbours." On [2, 7, 9, 3, 1] that takes 9 first, kills 7 and 3, then takes 2 and 1 for a total of 12 — which happens to be right here. But on [8, 10, 8] it grabs the 10, crosses out both 8s, and stops at 10. Yet the two 8s sit at indices 0 and 2, which are not adjacent, so taking both gives 16.

The pattern in both failures is the same: a choice that looks best right now can lock you out of a better choice later. When that is true, no fixed rule will do, and you have to compare the futures that each choice leads to.

I walk the street one house at a time. Standing at house i, I have two choices:

I keep the bigger of the two. The only thing I need to track is which house I'm standing at — one index.

f(i) = max( nums[i] + f(i-2), f(i-1) )

Base cases: f(0) = nums[0] — one house, take it. f(1) = max(nums[0], nums[1]) — two houses side by side, so keep the richer.

This point is worth a moment. When you rob house i and jump back to f(i-2), you are not demanding that house i-2 was robbed. You are only saying house i-1 was not. f(i-2) is the best plan over all houses up to i-2. None of those plans can touch house i-1, because i-1 is not in that range at all. So robbing i on top of f(i-2) is always legal. This is why one index is enough for the state: the "is my neighbour free?" question is answered by where the range ends, not by remembering what we picked.

The plain recursion writes itself. It is exponential for the usual reason: two branches per call, n deep, but only n truly different questions inside.

def rob(nums):
    def f(i):
        if i < 0: return 0
        if i == 0: return nums[0]
        return max(nums[i] + f(i - 2), f(i - 1))
    return f(len(nums) - 1)

The trouble is repetition. f(4) calls f(3) and f(2). But f(3) also calls f(2). So f(2) is computed from scratch more than once, and its answer never changes. There are only n different questions in here — f(0) through f(n-1) — yet the recursion asks them again and again. So keep a notebook. Before you compute f(i), check the notebook. If it is there, return it. If not, compute it once and write it down. That one change drops the work to O(n):

def rob(nums):
    memo = {}
    def f(i):
        if i < 0: return 0
        if i == 0: return nums[0]
        if i in memo: return memo[i]
        memo[i] = max(nums[i] + f(i - 2), f(i - 1))
        return memo[i]
    return f(len(nums) - 1)

Now remove the recursion and build the answers in an array instead. Keep the same meaning: let dp[i] hold exactly what f(i) returned — the most money you can rob from houses 0 through i. Then read the recurrence as an assignment. The recurrence said

f(i) = max( nums[i] + f(i-2), f(i-1) )

so, swapping each function call for an array read, the very same line becomes

dp[i] = max( nums[i] + dp[i-2], dp[i-1] )

It is the identical formula. We just store each result in a slot instead of returning it.

Which order do we fill the slots? dp[i] needs dp[i-1] and dp[i-2], both to its left. So if we fill left to right, both are ready by the time we reach i. No recursion, and no call stack.

That leaves the first two slots, which the formula cannot produce — it would reach back to indices -1 and -2, which do not exist. So we fill them by hand first:

With those two seeded, the loop starts at i = 2 and applies the formula the rest of the way:

def rob(nums):
    n = len(nums)
    if n == 1: return nums[0]
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, n):
        dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])
    return dp[n - 1]

Last, look at what one step of that loop actually reads: dp[i-1] and dp[i-2], never anything older. So the full array is wasted space — two variables hold everything the loop will ever look at. Keep two_back and one_back, slide them forward each step, and the memory drops to O(1):

def rob(nums):
    two_back, one_back = 0, 0
    for money in nums:
        current = max(money + two_back, one_back)
        two_back, one_back = one_back, current
    return one_back

Starting both variables at 0 lets the loop handle the first two houses without special cases. On the first pass, max(nums[0] + 0, 0) is just nums[0], which is right. On the second, max(nums[1] + 0, nums[0]) is the richer of the two, also right.

Answer 12, from houses 0, 2 and 4. Try the same walk on [5, 20, 6, 20, 5]: the running best yields 5, 20, 20, 40, 40, so the answer is 40. It correctly takes both 20s at indices 1 and 3, which are not adjacent to each other.

The idea that travels is not "houses". It is this: when a rule links neighbouring choices, decide at each position between taking it (and jumping back past the forbidden neighbour) and leaving it (and keeping the previous best). Whenever a problem says "you cannot pick two things next to each other", or "you must wait k turns after choosing", reach for this shape. The gap in the index is just how far the rule reaches.

Two natural twists test the same idea. If the street were a circle, the first and last houses would clash. The fix is to run this same routine twice — once without the last house, once without the first — and take the better result. If the houses formed a tree instead of a line, the same take-or-skip choice applies at each node; "skip past the neighbour" just becomes "skip past the children". Same idea, different shape of neighbourhood.