Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 63 ยท Dynamic Programming for Contests

Bitmask and Digit DP

Solve TSP-style bitmask DP, enumerate submasks in 3^n, assign tasks with dp[mask], and count numbers up to N with digit DP and the tight flag.

Two DP families look exotic at first, yet they follow the recipe from DP Problem Patterns exactly. Bitmask DP is for problems with a small set of items (usually n up to about 20) where the state must remember which items are already used. Digit DP is for questions of the form "how many integers up to N have property P?" where N may have 18 digits, far too many to loop over.

Both rely on a clever state, not on clever transitions. If bit operations feel unfamiliar, review Bit Tricks and XOR Problems and Bitmask DP first.

Bitmask DP: subsets as states

A subset of n items fits in an integer with n bits: bit i is 1 when item i is chosen. There are 2^n masks, and with n = 20 that is about a million states, which is feasible. Handy operations:

  • test bit: mask >> i & 1
  • add item: mask | (1 << i)
  • remove item: mask & ~(1 << i)
  • full set: (1 << n) - 1
  • number of items: mask.bit_count() (Python 3.10 and later)

The most famous example is the traveling salesman problem (TSP): visit every city exactly once and return to the start, with the smallest total distance. Brute force tries n! orders. The DP uses the state dp[mask][last]: the shortest route that starts at city 0, visits exactly the cities in mask, and ends at last. The transition adds one new city nxt that is not in the mask:

dp[mask | 1<<nxt][nxt] = min(dp[mask][last] + dist[last][nxt])

The time is 2^n * n * n, which beats n! easily: for n = 15 that is about 7 million steps instead of tens of billions of orders.

flowchart LR
    A["mask = {0}, last = 0"] --> B["mask = {0,2}, last = 2"]
    A --> C["mask = {0,1}, last = 1"]
    B --> D["mask = {0,1,2}, last = 1"]
    C --> E["mask = {0,1,2}, last = 2"]
    D --> F["add the edge back to city 0"]
    E --> F

States are (visited set, last city). Masks only grow, so increasing numeric order is a valid evaluation order.

Python TSP with a bitmask, checked against permutations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Assigning tasks: dp[mask] with an implicit position

Often one of the two state parts is implied by the other. Suppose n workers must each take a different task and cost[i][j] is worker i doing task j. If mask is the set of tasks already assigned, then exactly mask.bit_count() workers have been placed, so the next worker is i = mask.bit_count(). The state is just dp[mask] and the time is 2^n * n.

Enumerating submasks

Some problems need every subset of a given set. The loop

Python
sub = mask
while sub:
    # use sub
    sub = (sub - 1) & mask

visits every non-empty submask of mask exactly once. Summed over all masks, each of the n items is in one of three states (not in mask, in mask but not in submask, in both), so the total work is 3^n, not 4^n. That is why "partition into groups" problems with n up to 15 or so are possible.

Python Assignment DP and submask enumeration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Digit DP

Now a very different style of problem: count the integers x in [0, N] whose digits satisfy some rule. For N = 10^18 you cannot test each number. Digit DP builds numbers from the most significant digit to the least, and remembers just enough about the digits chosen so far.

The usual state is (position, tight, extra):

  • position: how many digits we have placed.
  • tight: is the prefix so far equal to the prefix of N? If yes, the next digit is limited to N's digit at that position; if no, it can be anything from 0 to 9. Once we place a smaller digit than N's, we are free forever.
  • extra: whatever the rule needs, such as the sum of digits so far, the previous digit, or a remainder modulo m.

Two other tricks come up often. A started flag handles leading zeros (for rules where "007" must not look like three digits). And a range [L, R] is answered as count(R) - count(L - 1).

The recursion is memoized with lru_cache. Only states with tight = False repeat, so the cost is about positions * extra_values * 10.

Python Digit DP: digit sum and no equal neighbors

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at count_digit_sum(10**18, 90). Numbers up to 10^18 have at most 19 digits, so there are astronomically many candidates, yet the DP answers instantly because it tracks only about 19 positions times 91 remaining sums, never the numbers themselves.

How to choose between them

Signal in the statement Technique
n at most about 20, "each item at most once", order or grouping matters Bitmask DP
"Partition into groups", n at most about 15 Submask enumeration (3^n)
"Count numbers up to N" with a digit property, N up to 10^18 Digit DP
Count pairs (a, b) in a range with a digit property Digit DP over two numbers at once (two tight flags)

Sum over subsets (SOS DP)

Bitmask DP often needs the following aggregate: for every mask m, compute g[m], the sum of f[s] over all submasks s of m. Doing it directly costs 3^n in total, since each mask visits all its submasks. SOS DP (sum over subsets, also called the zeta transform on subsets) does it in n * 2^n.

The idea is to add one bit at a time. After processing bits 0..b, g[m] holds the sum over submasks that differ from m only in those low bits. To extend by bit b: if m has bit b set, add g[m without b], because the submasks that lack bit b are not yet counted. Loop over bits on the outside, masks on the inside, and update in place.

Variants and uses:

  • Supersets: flip the condition (if bit b is not set, add g[m | bit]).
  • Inverse (Mobius transform): subtract instead of add to recover f from g. This is inclusion-exclusion on masks.
  • Counting: with f[x] = number of array elements equal to x, g[m] is the number of elements that are submasks of m. That answers "how many elements are contained in this one?" for all elements at once.
  • Pairs with a[i] & a[j] == 0: a[j] must be a submask of the complement of a[i], so the count for a[i] is g[~a[i]].
  • Maximum or minimum instead of the sum, when you need "best value among submasks" (SOS DP works for any commutative, idempotent or invertible combination, as long as you do not double count).
Python SOS DP: subset sums, supersets and AND = 0 pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cost is n * 2^n regardless of how many masks are actually used, so it fits up to about n = 20 in C++ and n = 16 in plain Python. The brute force in the test is the 3^n loop, and the inverse transform is checked by recovering the original array.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the TSP bitmask DP, what does dp[mask][last] mean?

    The mask records which cities are used and last records where we stand, which is all the future needs to know.
  2. 2. Why does enumerating all submasks of all masks of n bits take about 3^n steps?

    Each of the n items has three possibilities, so the number of (mask, submask) pairs is 3^n.
  3. 3. In digit DP, what does the tight flag tell us?

    While tight, we must not exceed N. After choosing a smaller digit the flag turns off and all digits 0 to 9 become allowed.
  4. 4. How do you count integers in [L, R] with a digit property using a function count(N)?

    count(N) covers [0, N] (or [1, N]), so subtracting the part below L leaves exactly the range [L, R].

Summary

  • Bitmask DP stores a subset of up to about 20 items in one integer; TSP uses dp[mask][last] in O(2^n * n^2).
  • When one state part is implied (the number of set bits gives the next worker), dp[mask] alone is enough.
  • sub = (sub - 1) & mask enumerates submasks; all masks together cost 3^n.
  • Digit DP walks digits from the most significant one with a tight flag, an optional started flag, and the rule's extra state.
  • Answer a range with count(R) - count(L - 1), and always check against direct counting for small N.
  • SOS DP computes sums over all submasks (or supersets) of every mask in n * 2^n, and its inverse recovers the original values.

Next: DP Speedups