CodeWithYash

Advanced · Module 18 · Lesson 10

Bitmask & digit DP

Encode subsets or prefix constraints in state.

15–25 min readLesson 114 of 123

Lesson 114 of 123

1d streak

Theory lesson · Step-by-step

Understand Bitmask & digit DP

Encode subsets or prefix constraints in state.

Worked approach

Trace the reasoning step by step

  1. 1Define the minimal state variables needed by Bitmask & digit DP.
  2. 2Write the recurrence as choices from smaller states.
  3. 3Set base cases for the smallest reachable states.
  4. 4Choose memoization or an evaluation order in which dependencies are ready.
  5. 5Return the requested state, then optimize memory only if dependency order permits.

Concrete example

Track used tasks among three choices.

  1. 1Mask 000 means none used.
  2. 2Choosing task 1 sets bit 1 → 010.
  3. 3Transitions only choose zero bits.

A 3-bit mask represents all 2³ subsets compactly.

What must remain true (Loop Invariant)

Every state consumed by Bitmask & digit DP already stores the correct answer for its declared subproblem, so each transition uses only valid dependencies.

Cost Model

Complexity & Trade-offs

Encoded state search
O(states × transitions)
O(states)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Optimization, counting, and feasibility with overlapping subproblems.
  • Sequence, grid, interval, tree, subset, and digit constraints.
  • Replacing exponential recursion with reusable state.

Common mistakes

  • Defining a state that lacks information needed by the transition.
  • Iterating in an order that reads unresolved or same-round values.
  • Optimizing space before proving dependencies.

Practice prompts

  • Reproduce the worked Bitmask & digit DP example without looking at the trace.
  • Change one input condition and explain whether the Bitmask & digit DP invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.