Bitmask DP
Encode the set of used items as bits of an integer and memoise over the mask.
Dynamic ProgrammingO(2^n * n)New3 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
n is at most 20
travelling salesman
assign tasks to people
cover all items
The template
Get this into muscle memory, then adapt the condition per problem.
for (let mask = 0; mask < (1 << n); mask++)
for (let i = 0; i < n; i++)
if (mask & (1 << i))
dp[mask] = best(dp[mask], dp[mask ^ (1 << i)] + cost(i, mask));If you are stuck
The generic hint ladder for this pattern, in order.
- 1A tiny n with subset semantics points straight at bitmasks.
- 2The mask is the state, each bit meaning used or not.
- 3Subset sum over masks lets you split a set into two halves.
Drill it
Every problem in the bank that uses this pattern.
0 / 3 solved