Pattern 2: Include or exclude

A huge family of DPs boils down to a repeated decision: at each item, take or skip? The optimal answer is the better of the two choices — and that is the essence of decision DP.

🎯

Try it first: House Robber

Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.

Houses in a row, each with a value in nums. You cannot rob two adjacent houses. Return the maximum you can rob.

Example: [2,7,9,3,1] → 12 (rob houses 2, 9, and 1 → 2+9+1).

Carregando editor…

Tried it? The rule "you can't rob adjacent houses" creates the decision: if I rob house i, I can't have robbed i-1. The theory below turns this into a simple recurrence.

The theory: the better of take and skip

In House Robber, when you reach house i, there are two options:

Skip house i: the best stays whatever you had up to i-1.
Rob house i: you gain nums[i], but the best allowed before is the one at i-2 (you can't take the adjacent i-1).

The answer for i is the maximum of these two choices:

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

It's the same 1D shape from the previous lesson, but now the recurrence expresses a decision (max between include and exclude). And, since it only depends on i-1 and i-2, you can do it in O(1) space (two accumulators). Note the echo of Kadane (Array): "extend or restart" was also a local decision — DP has always been nearby.

House Robber II: the houses in a circle

What if the houses form a circle (the first and the last are adjacent)? The trick is to reduce it to the problem you already solved: either you don't rob the first house, or don't rob the last — so run the linear House Robber twice (on nums[0..n-2] and on nums[1..n-1]) and take the larger. Reusing the linear solution as a building block is a powerful pattern.

Greedy vs DP: the boundary (Jump Game)

Not every decision problem needs DP — sometimes a greedy suffices, and it's cheaper. Jump Game ("can you reach the end, given that each position tells the maximum jump?") has a natural DP, but a greedy O(n)/O(1) solves it: walk through, tracking the farthest reachable position; if it never falls behind the current position, you can make it.

Carregando editor…

When should you prefer greedy over DP? When a locally optimal choice leads to the global one (and you can prove it, like the exchange argument in the Intervals section). When you can't — when you need to compare several choices and remember results — it's DP. When in doubt, DP is the safety net: it always works, even if it sometimes does more work than a greedy.

🧠 Review quiz

0/4

1. What is the House Robber recurrence and what does each part mean?

2. In House Robber II (houses in a CIRCLE), how do you reuse the linear solution?

3. Jump Game has a greedy O(n) solution. When can a greedy replace DP?

4. Which pattern from an earlier section was actually a decision DP?

Summary

Decision DP: at each item, include or exclude → dp[i] = max(exclude, include).
House Robber: max(dp[i-1], nums[i] + dp[i-2]), O(n)/O(1).
House Robber II: run the linear one twice (without the 1st / without the last).
Greedy vs DP: greedy when the local choice guarantees the optimum; DP when you need to compare and remember.

Next lesson: composing a target from reusable items — knapsack.

All lessons in this section