AdvancedDynamic Programming

Bitmask DP

DP over subsets for assignments, TSP-like problems, and state compression

Time: O(poly(n) 2^n)
Space: O(2^n)
Pattern Overview

Core Idea

Use bitmasks to represent chosen sets; transitions add/remove one element.

When to Use

Use when n ≤ 20–25 and state is combinatorial over subsets.

General Recognition Cues
General indicators that this pattern might be applicable
  • Subset enumeration
  • Assignment cost
  • Traveling over states
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

TSP

Visit all nodes with minimal path

When to Use This Variant
  • All visited mask
Use Case
Shortest tour
Advantages
  • O(n^2 2^n)
Implementation
def tsp(dist):
    n=len(dist); INF=10**9
    dp=[[INF]*(1<<n) for _ in range(n)]
    dp[0][1]=0
    for mask in range(1<<n):
        for u in range(n):
            if not (mask>>u)&1: continue
            if dp[u][mask]==INF: continue
            for v in range(n):
                if (mask>>v)&1: continue
                dp[v][mask|1<<v]=min(dp[v][mask|1<<v], dp[u][mask]+dist[u][v])
    ans=min(dp[u][(1<<n)-1]+dist[u][0] for u in range(n))
    return ans
2

Assignment

Match tasks to agents

When to Use This Variant
  • Mask of assigned
Use Case
Min cost match
Advantages
  • Straightforward memo
Implementation
def assignment(cost):
    n=len(cost)
    from functools import lru_cache
    @lru_cache(None)
    def dp(i, mask):
        if i==n: return 0
        best=10**9
        for j in range(n):
            if not (mask>>j)&1:
                best=min(best, cost[i][j]+dp(i+1, mask|1<<j))
        return best
    return dp(0,0)
3

DP over Subsets

Iterate submasks/supersets

When to Use This Variant
  • Submask enumeration
Use Case
OR/AND DP
Advantages
  • FFT-like transforms optional
Implementation
def or_subsets_dp(f):
    # f[mask] holds initial values; compute F[mask]=sum of f[sub] over submasks
    n=(len(f)-1).bit_length(); F=f[:]
    for i in range(n):
        for mask in range(1<<n):
            if mask&(1<<i): F[mask]+=F[mask^(1<<i)]
    return F
Common Pitfalls
Watch out for these common mistakes
  • State explosion
  • Bit ops indexing
  • Memoization keys
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(poly(n) 2^n)

Subset DP costs exponential but manageable for n≤20.

Space Complexity
O(2^n)

Memo tables keyed by mask.

Ready to test your knowledge?

Test your pattern recognition with interactive questions