Dynamic Programming

Bitmask DP

State includes the set of used items encoded as bits (n ≤ 20).

Hard, optional depth, about 120 minutes to practise.

1Understand

The idea

When n is at most about 20, represent "which items are used" as the bits of an integer. dp[mask] (or dp[mask][last]) is the best result using exactly that set. Transitions add one unused item with mask | (1 << i), for O(2ⁿ · n) or O(2ⁿ · n²) in total.

Intuition

When n is at most about 20, represent "which items are used" as bits of an integer. dp[mask] (or dp[mask][last]) is the best result using exactly that set of items.

Transitions add one unused item with mask | (1 << i). Iterate masks in order, or recurse with memo on the mask. Total states 2ⁿ or n·2ⁿ.

Bit tricks (mask & -mask, iterate submasks) show up in advanced variants.

What you will be able to do

  • Encode sets as integers
  • Add the last element to the state when needed

When to use it

  • Visit every node once (small n)
  • Assign n tasks to n workers
  • n ≤ 16-20 with "all subsets"

2See it

Walkthrough

TSP-style mask DP

4 cities, mask bits = visited; start mask = 0001 (city 0).

1 / 4

mask0
mask1
mask2
mask3
0123

dp[1<<0][0] = 0. Bit i set means city i is in the tour so far.

dp[1 << start][start] = 0

Live template

Line 1 active

1dp = [inf] * (1 << n); dp[0] = 0
2for mask in range(1 << n):
3 for i in range(n):
4 if not mask & (1 << i):
5 dp[mask | 1 << i] = min(dp[mask | 1 << i], dp[mask] + cost(mask, i))

Complexity: time O(2^n · n), space O(2^n)

O(n² · 2ⁿ) for TSP-like, O(n · 2ⁿ) for simpler masks. Impossible for n = 40; then need meet-in-the-middle or a different model. Space O(n · 2ⁿ) can be the limiter before time.

Read the walkthrough as text

TSP-style shortest path through all cities. n = 4 cities, start at 0.

  1. dp[1 << 0][0] = 0, at city 0 with only 0 visited.
  2. From each (mask, u), try edge u→v if bit v off: update dp[mask|1<<v][v].
  3. Answer is min over dp[(1<<n)-1][v] + dist[v][0] to return home.
  4. 2⁴ · 4 states, each with ≤4 transitions.

Assignment problems use dp[mask] = min cost assigning bit-set workers to the next job.

3Recognise it

Kinds of problems (6)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Assignment problems

    Example. Assign n workers to n jobs minimum cost.

    How. dp[mask] = min cost covering mask; try add job j with worker popcount(mask).

  • Travelling salesman (mask + last node)

    Example. Shortest tour visiting all cities once.

    How. dp[mask][i] ending at i; transition from prev j by adding edge cost.

  • Partition into k subsets

    Example. Split items into k groups with equal sum (small n).

    How. Bitmask + target sum per group; backtrack or DP on masks.

  • Shortest path visiting all nodes

    Example. Visit every node in small graph.

    How. TSP / BFS on (node, mask) state space.

  • Mask over the letters still needed (stickers)

    Example. Spell target using sticker subsets.

    How. dp[mask] letters covered; try each sticker OR into mask.

  • Game states over used items (can I win)

    Example. Turn game picking stones, win from mask.

    How. dp[mask] winnable if any move leaves opponent losing state.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Operator precedence

    Why it happens. `&` and `<<` without parens looks fine on paper.

    How it fails. mask & 1 << i == 0 parses as mask & (1 << i == 0), wrong branch logic.

    Fix. Parenthesise: (mask & (1 << i)) == 0.

  • State too small

    Why it happens. Mask alone encodes visited set for TSP transitions.

    How it fails. TSP dp[mask] only, cannot know which city you are at to extend tour.

    Fix. Add last-node dimension: dp[mask][i] ending at city i.

  • n too large

    Why it happens. 2^n table is the textbook solution for subset DP.

    How it fails. n=25 → 2^25 states, memory blow-up; need different algorithm.

    Fix. Bitmask DP only when n ≤ ~20 (problem dependent).

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons