Bitmask Dynamic Programming

State dp[mask] often means “best cost after visiting set mask of cities/items.” Transitions add one bit at a time.

Try this in Python

n = 3
INF = 10**9
dp = [INF] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
    for j in range(n):
        if (mask >> j) & 1:
            continue
        nxt = mask | (1 << j)
        dp[nxt] = min(dp[nxt], dp[mask] + 1)
print(dp[(1 << n) - 1])

Key takeaways

• TSP-style assignment uses bitmask DP when n ≤ 20 roughly.
• Layer graph on (pos, mask) for clarity.
• Memory can be rolling row if only previous layer matters.