Skip to content

Sets and States (Beginner)

Dynamic programming scares people. The recurrences look cryptic, the tables feel arbitrary, and nobody explains how you come up with the state in the first place.

This page strips DP down to two ideas: what are you collecting? and what summary do you keep? That's all a DP state is — a summary of a collection. Once you see that, the mystery disappears.

Collections Are Everywhere

Before worrying about DP, notice that you already work with collections all the time:

  • A visited array in BFS → a collection of "nodes I've seen"
  • A hash map in Two Sum → a collection of "values I've encountered"
  • A prefix sum array → a collection of "running totals"

Each of these is a container — something that holds objects. The specific data structure (array, set, map) is a choice you make after you know what you're collecting.

The first question in any problem isn't "which data structure?" It's "what am I collecting?"

DP States Are Summaries

Here's the key insight: a DP state is a compressed summary of your collection. You don't store everything — you store just enough to make the next decision.

Example: Coin Change

What's the minimum number of coins to make amount \(N\)? Coins: [1, 3, 5].

Your "collection" at any point is the coins you've used so far. But you don't need to know which coins — only how much they add up to. So the summary is:

dp[amount] = minimum coins needed to reach this amount.

Amount 0 1 2 3 4 5 6
Min coins 0 1 2 1 2 1 2

For amount 6: use coins 1+5 (2 coins) or 3+3 (2 coins). Either way, dp[6] = 2.

The transition: for each coin \(c\), check if dp[amount - c] + 1 is better than what you have.

dp[6] = min(dp[6-1]+1, dp[6-3]+1, dp[6-5]+1)
      = min(dp[5]+1, dp[3]+1, dp[1]+1)
      = min(2, 2, 2) = 2

Notice: the state is just the remaining amount. Not which coins you used. Not the order. Just the amount. That's the summary.

Example: Climbing Stairs

You can climb 1 or 2 stairs at a time. How many ways to reach stair \(N\)?

Your "collection" is the sequence of steps you've taken. But all you need to know is where you are now. Two different step-sequences that both end at stair 5 give exactly the same future options.

dp[i] = number of ways to reach stair \(i\).

dp[0] = 1  (you're already there)
dp[1] = 1  (one way: take 1 step)
dp[2] = dp[1] + dp[0] = 2  (either 1+1 or 2)
dp[3] = dp[2] + dp[1] = 3
dp[4] = dp[3] + dp[2] = 5

The transition: dp[i] = dp[i-1] + dp[i-2]. You either came from one step below or two steps below.

How to Find the State: The Noun Technique

Here's a practical method. Read the problem statement and pull out every noun — every thing being counted, measured, limited, or tracked.

Example: Cheapest Flights Within K Stops

Find the cheapest flight from city A to city B with at most K stops.

Nouns: city, cost, stops.

Which of these change as you make decisions? - City changes (you fly somewhere) - Stops changes (you use one per flight) - Cost changes (you pay for the flight)

Which determines your future options? - Where you are (city) — determines which flights you can take - How many stops you've used (stops) — determines if you can keep going

What are you optimizing? - Cost — that's the value you store, not a parameter

So the state is: dp[city][stops_used] = minimum cost to reach this city with this many stops.

That's it. You didn't need to know this is "Bellman-Ford" or any algorithm name. You just listed the nouns and asked which ones matter.

Two Ways to Build: Add or Merge

When you're building a DP solution, you're always doing one of two things to your collection:

Add one element

Take your existing solution and extend it by one item.

  • Knapsack: consider the next item. Take it or skip it.
  • LIS: try extending the subsequence by one more element.
  • Coin change: add one more coin.

The transition looks like: dp[i] = f(dp[i-1], current_element).

Merge two solutions

Combine two independent partial solutions into one.

  • Segment tree: merge left half's answer with right half's answer.
  • Interval DP: split a range into two parts, solve each, combine.

The transition looks like: dp[L][R] = f(dp[L][M], dp[M+1][R]).

Most beginner DP problems use the "add one element" approach. The "merge" approach shows up in more advanced problems.

Bitmask DP: When Your Collection Is Small

Sometimes your collection is a set of items — which ones have you used? If the set is small (up to ~20 items), you can encode it as a number.

The idea: use a binary number where bit \(i\) is 1 if item \(i\) is in the set, 0 if not.

Set {0, 2, 4} → binary 10101 → decimal 21
Set {1, 3}    → binary 01010 → decimal 10
Set {}        → binary 00000 → decimal 0

Now "the set" is just an integer, and you can use it as a DP index.

Example: You have 4 tasks and 4 workers. Each worker does each task at different speeds. Assign tasks to minimize total time. There are \(4! = 24\) permutations to try.

With bitmask DP: dp[mask] = minimum time when the set of assigned tasks is mask, and the next worker to assign is determined by how many bits are set.

For 4 tasks, mask ranges from 0 to 15 (\(2^4 - 1\)). That's only 16 states — much less than 24 permutations. For 20 tasks, \(2^{20} \approx 10^6\) states vs \(20! \approx 10^{18}\) permutations. The savings are astronomical.

Common Mistakes

Too much in the state. If you track every detail, the state space explodes. Ask: "do I really need to know this for future decisions?" If not, drop it.

Too little in the state. If you can't write a valid transition — if knowing the current state isn't enough to decide the next move — you're missing a parameter. Add it.

Confusing the value with the state. The thing you're optimizing (min cost, max profit, number of ways) is the value stored at each state, not a parameter of the state. Don't put it in the index.

Practice Problems

Start with these. For each one, identify the nouns, pick the state, write the transition.

1. Climbing Stairs (LC 70)

State: dp[i] = ways to reach stair \(i\). Transition: dp[i] = dp[i-1] + dp[i-2].

2. Coin Change (LC 322)

State: dp[amount] = min coins for this amount. Transition: for each coin \(c\), dp[amount] = min(dp[amount], dp[amount-c] + 1).

3. House Robber (LC 198)

State: dp[i] = max money robbing from houses \(0..i\). Transition: dp[i] = max(dp[i-1], dp[i-2] + money[i]). You either skip house \(i\) or rob it (but then you can't rob \(i-1\)).

4. 0/1 Knapsack

State: dp[i][w] = max profit using items \(1..i\) with capacity \(w\). Transition: skip item \(i\) (dp[i-1][w]) or take it (dp[i-1][w-weight] + profit).

5. Cheapest Flights Within K Stops (LC 787)

State: dp[city][stops] = min cost to reach this city with this many stops. Process layer by layer (like BFS by number of stops).

Ready for more? The full versions cover bitmask DP in depth, lazy operations, small-to-large merging, LIS optimization with binary search, and the art of state design: