house-robber

Difficulty: Medium  ·  Topic: 1-D Dynamic Programming  ·  Practice it on parikshan: /practice/house-robber/start

The story

A real-time ad-bidding service evaluates a stream of auction slots throughout the day. Each slot has an expected payout v[i] (predicted click-through value, after bid shading), but the platform enforces a rate-limit policy on a given bidder: no two adjacent auctions can be won by the same campaign, to prevent burst spend and viewer fatigue. The campaign manager asks: given the per-slot expected payouts, what is the maximum total payout the bidder can realise across the day without ever winning two adjacent slots?

That is house-robber. Once you see the shape, it appears everywhere a sequence forbids "consecutive picks": weighted-interval scheduling in resource allocation, exclusive marketing pushes where two adjacent slots conflict, banner rotations where neighbouring placements must differ.

What's actually being asked

You have an array v of length n where v[i] is the value at position i. Select a subset of positions that maximises the sum, subject to the constraint that no two adjacent positions are both selected. Return the maximum sum.

Examples:

• v = [1, 2, 3, 1] → 4. Pick positions 0 and 2 (1 + 3 = 4).
• v = [2, 7, 9, 3, 1] → 12. Pick 0, 2, 4 (2 + 9 + 1 = 12). Picking 1 and 3 gives only 10.

The naive approach

For each index, branch on pick-or-skip:

def best(i, v):
    if i >= len(v): return 0
    return max(best(i+1, v), v[i] + best(i+2, v))

Exponential. For n = 30 it already hits ~10⁹ calls. For n = 100000 you wait until the heat death of the universe.

The key insight

At index i, you have exactly two choices: skip it (best so far is unchanged from i-1) or rob it (best is whatever was best at i-2, plus v[i]). Take the maximum. That single line of arithmetic is the whole algorithm.

# Recurrence:
# dp[i] = max loot achievable using only positions 0..i
# dp[-1] = 0   (no positions, no loot)
# dp[0]  = v[0]
# dp[i]  = max( dp[i-1] , dp[i-2] + v[i] )   for i >= 1
# Answer = dp[n-1]

The four DP questions:

1. State: dp[i] is the maximum loot using positions [0..i], with the no-adjacency rule respected.
2. Base case: dp[0] = v[0]. (Alternatively define dp[-1] = 0 and dp[0] = v[0] to make the recurrence uniform.)
3. Transition: dp[i] = max(dp[i-1], dp[i-2] + v[i]). Either skip i or rob it.
4. Answer: dp[n-1].

Step-by-step approach

Bottom-up, O(n) time, O(n) space:

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

Only the previous two values matter. Collapse to two scalars:

def rob(v):
    prev2, prev1 = 0, 0
    for x in v:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

O(n) time, O(1) space. The trick is to let prev1 always be dp[i-1] and prev2 always be dp[i-2], and update both each iteration.

Worked example

v = [2, 7, 9, 3, 1]

Return 12. Verified.

Complexity

• Time: O(n).
• Space: O(1) with the two-scalar form, O(n) with the array form.

Common pitfalls

• The seductive greedy: "always pick the largest, then skip its neighbours, repeat" fails on [2, 1, 1, 2]. Greedy picks the first 2, must skip, picks neither neighbour, then skips the last 2 because the third position was skipped. Total 2. Optimum: 2 + 2 = 4. The constraint couples decisions across the whole array; greedy cannot see far enough.
• Confusing the recurrence direction: do not write dp[i-2] + v[i-1]. The current value is v[i], and the safe predecessor is dp[i-2].
• Negative values: this problem guarantees v[i] >= 0, but if a variant allowed negatives, "skip" might dominate everywhere and the answer could be zero. The recurrence still works.
• Off-by-one on dp[1]: dp[1] = max(v[0], v[1]), not v[1]. You may always choose to skip position 1 in favour of position 0.

Where this shows up in the enterprise

• Ad-bidding rate-limit allocation: as in the opening story. Bidders cannot win two adjacent slots for the same campaign; maximise expected payout across the day.
• Weighted-interval scheduling on uniform-length slots: pick a set of jobs to run on a single resource such that no two are in adjacent time-buckets. Maintenance windows, batch-job lanes, exclusive-feature roll-outs.
• Exclusive marketing push scheduling: a campaign cannot fire pushes on consecutive days to the same audience cohort; maximise opens.
• Replenishment cadence with intake-throughput limits: schedule warehouse restocks so no two arrive on adjacent days when the dock has only one bay; maximise inventory coverage.
• Banner-rotation slot picking: adjacent banners must differ by theme; pick the most engaging non-adjacent subset within a single rail.
• Driver-shift recommenders: avoid double-shifting back-to-back periods to respect fatigue rules; maximise earnings.
• Per-stay promotion stacking: cannot apply two promotions on consecutive nights of a booking; maximise total booking revenue across the stay.
• Genome-assembly k-mer selection: when adjacent k-mers overlap and only one can be "anchored" per neighbourhood, the recurrence is exactly this.

Whenever you see "pick a subset, no two adjacent, maximise/minimise sum", this is the answer.

Variants you'll see elsewhere

• house-robber-ii: the houses are arranged in a circle, so the first and last are adjacent. Run the linear DP twice, once excluding the first house, once excluding the last, take the max.
• house-robber-iii: the houses are arranged in a binary tree. The recurrence becomes (skip, take) returned by each subtree; the parent combines children's take and skip results.
• delete-and-earn: bucket values by frequency, then this exact DP on the bucket array; "deleting x" forbids deleting x-1 and x+1.
• maximum-sum-non-adjacent-subsequence: same problem, different name.
• paint-house: a multi-state variant where the constraint is "not the same colour as the previous one".

The whole "pick-or-skip with bounded look-back" family lives off the same recurrence.

How parikshan turns this into a learning loop

house-robber is the first medium problem in the DP ladder, and the integrated learning loop pays its highest dividends here.

1. Read this article, then state the recurrence in English before writing code. dp[i] = max(dp[i-1], dp[i-2] + v[i]). If you cannot say that sentence, you cannot write the code, and AI cannot save you.
2. Practice mode with no AI: write the array version first, then collapse to O(1). The bank's dynamic test on this problem includes [2, 1, 1, 2] and [5, 5, 10, 100, 10, 5], which catch the greedy failure mode within seconds.
3. AI training: Find Bugs. If your code returns the wrong answer on [2, 1, 1, 2], paste it in. The assistant should point at the greedy or off-by-one error. This trains your eye to spot the failure pattern.
4. AI training: Optimise. Once correct, ask for the O(1) space rewrite. Verify the two-scalar form does the same thing as your array version on [2, 7, 9, 3, 1].
5. Exam mode: redo cold. When you can solve house-robber from scratch in under five minutes without AI, the pattern is in your fingers.
6. Dispute only for adversarial test failures you cannot explain. DP problems have unambiguous verdicts.

In the AI-integrated workspace

AI assistants love to write greedy solutions to this problem. Watch for it.

• The greedy trap: an agent often produces "sort by value descending, pick the largest, mark neighbours forbidden, repeat". This is fast, looks reasonable, and is wrong on roughly 30% of inputs. If you let it ship, your tests will pass on [1, 2, 3, 1] (greedy happens to be right) and fail in production on [2, 1, 1, 2].
• The off-by-one trap: an agent writes dp[i-2] + v[i-1] because it confused "two back" with "previous". The code returns slightly too-low answers on small inputs that often slip through casual testing.
• The wrong base case: dp[1] = v[1] instead of max(v[0], v[1]) is a single-character bug that produces wrong answers on [5, 1, ...].

The 2027 engineer's discipline:

1. State the recurrence in English before generating code. "dp[i] is the best loot using positions 0..i. dp[i] = max(skip this house = dp[i-1], rob this house = dp[i-2] + v[i])."
2. Tell the agent to implement that recurrence. Not "solve house robber"; give it the recurrence.
3. Verify on [2, 1, 1, 2]. Always. Any agent that produces 3 (greedy) is wrong. The only acceptable answer is 4.
4. Demand O(1) space. If the agent cannot collapse to two scalars cleanly, the recurrence is not solid in its head.

That discipline turns a probabilistic generator into a deterministic verified result, and house-robber is one of the cheapest places to drill it.