Bit manipulation and bitmask state · HTML
dp[mask] is the optimum after completing exactly mask; add i with next=mask|(1<<i), or remove a chosen last item in the reverse recurrence.
Recognition signals
- n is small but orderings or matchings explode
- The future depends on the used set
- Different paths reach the same set
- Every item is visited once
- Assignment, pairing, or tour-like states appear
False friends
| Signal | Why it is different |
|---|
| Unencoded history affects the future | If last position or remaining resource changes transitions, add that dimension. |
| n is too large | The 2^n state space is itself infeasible; seek structure or another algorithm. |
Core invariant
dp[mask] is optimal among all legal sequences producing exactly mask, and transitions start from already-correct smaller states.
State, transition, and processing order
| Item | Definition |
|---|
| State | An array of length 2^n, with the minimum sufficient extra dimensions such as last or remaining capacity. |
| Transition | For each unused i, relax dp[mask|1<<i] with dp[mask]+transition_cost(mask,i). |
| Frontier / order | Sets progress by increasing popcount; every predecessor has one fewer item, forming a DAG. |
Python skeleton
def min_order_cost(n, step_cost):
inf = float('inf')
dp = [inf] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
if dp[mask] == inf: continue
for i in range(n):
if mask >> i & 1: continue
nxt = mask | (1 << i)
dp[nxt] = min(dp[nxt], dp[mask] + step_cost(mask, i))
return dp[-1]
Correctness sketch
- The empty-set base state is optimal.
- Every nonempty construction has a last-added item whose removal gives a smaller predecessor.
- Enumerating all predecessors and final choices covers every legal construction.
- Taking min preserves the best path to each mask, proving the full-mask optimum by induction.
Complexity
| Time | Space | Parameters |
|---|
| Typically O(n2^n), or O(n²2^n) with a last dimension | O(2^n) or O(n2^n) | n selectable items |
Edge cases
- Initialize dp[0]
- Keep unreachable states at infinity
- For n=0 the full mask is zero
- Negative costs are safe because the state graph is acyclic
- Ask whether last is derivable from mask
Error patterns
| Pattern | Why it fails / fix |
|---|
| Insufficient state | Two paths with the same mask cannot merge if different last items change the future. |
| Selecting an item twice | Check that its bit is clear before transition. |
| Propagating infinity | Skip unreachable states to avoid pollution or overflow. |
Selection and exclusion rules
- Future depends only on the chosen set: dp[mask].
- Future also depends on endpoint: dp[mask][last].
- Enumeration without optimization: plain bitmask enumeration.
- Above roughly low twenties, estimate resources and seek more structure.
Original micro-example
| Part | Detail |
|---|
| Result | Eight masks reuse all orderings that reach the same set. |
| Scenario | Three tasks have costs depending on the previously completed set. |
| Walkthrough | Mask 011 comes from 001 plus task 1 or 010 plus task 0; dp[011] retains the cheaper route. |
Recall prompts
My notes