Why does subset DP over a courier's route need dp[mask][last] rather than dp[mask] alone?
answer
- what does the next leg's cost depend on
- same set of sites, different place to stand
- a state must screen off the past
- two partial routes, same mask, not comparable
- index the table by endpoint as well
basics
~20 sThe visited set alone does not determine the remaining cost: the next leg's travel time depends on which site the courier is standing at. dp[mask][last] carries both the set of visited sites and the current position.
solid answer
~40 sA DP state must make the future independent of the path taken to reach it. For a courier who must visit every client site once and return to the depot, two partial routes can cover the *same* set of sites and yet leave the courier in different places — and the cost of everything that follows depends on where they are standing. So the set is not a sufficient state. The fix is a second index: `dp[mask][last]` = cheapest way to have visited exactly the sites in `mask`, finishing at site `last`. The transition extends by one unvisited site: `dp[mask | bit(j)][j] = min(dp[mask][i] + travel[i][j])`. That gives 2^n·n states and O(n) work per state, so O(2^n·n^2) time and O(2^n·n) memory. The answer is the minimum over `last` of `dp[full][last] + travel[last][depot]`.
go deeper
Recall the shape: an integer's bits stand for 'visited or not', and the table is indexed by that integer plus the current position. Be able to say why enumerating every ordering is hopeless past a dozen or so items.
Explain out loud why the visited set alone fails as a state, write the transition, and derive 2^n·n states with O(n) work each. Interviewers at this level want the recurrence and the cost, not code.
Show judgment about when the endpoint dimension is actually required versus redundant, and be ready to discuss memory layout, reconstruction of the route, and what asymmetric costs do and do not change.
Own the framing: this is an exact method with an exponential memory wall, so the interesting call is where it belongs in a system at all — on small clusters of stops, as an oracle for testing an approximate planner, or nowhere.
## The problem shape A courier starts at a depot, must visit each of n client sites exactly once, and returns to the depot. Travel times between every pair of locations are known and may be asymmetric (one-way streets, traffic direction). You want the cheapest closed route. Brute force enumerates n! orderings — at n = 18 that is about 6.4 × 10^15, hopeless. Subset DP replaces "which ordering" with "which set, and where am I now", and that collapse is the whole trick. ## What a bitmask is doing here A *bitmask* is an integer used as a set: bit i is 1 when site i has been visited. With n sites there are exactly 2^n such sets, and each is a single integer you can index a table with. That is the only reason subsets are usable as a DP dimension at all — the set is a number, so the table is a plain lookup rather than a map of sets. ## Why the set alone is not a state The defining property of a DP state is that it must **screen off the past**: everything the remaining decisions cost has to be computable from the state, never from how you got there. Suppose the mask says sites {A, B, C} are done. One partial route ended at A, another ended at C. Those two histories have different futures — the very next leg is priced from a different starting point, and so is every leg after it. Storing one number per mask would force you to compare, and discard, routes that are not comparable: the cheaper prefix may end somewhere expensive to leave. Keeping only the cheaper one silently throws away the optimum, and the DP returns a wrong (too small or unachievable) answer rather than a slow one. Adding the endpoint restores the property. Once you know the visited set *and* the current site, the rest of the trip depends on nothing else — the identity of the remaining sites is `complement(mask)`, and the first leg out is priced from `last`. That is optimal substructure recovered. ## The recurrence Fix the depot as the start so it never occupies a bit (fixing the start also removes the n-fold rotational symmetry of a closed tour for free). - Base: `dp[bit(i)][i] = travel[depot][i]` for every site i. - Transition: for each mask, each `i` set in mask with a finite `dp[mask][i]`, and each `j` not in mask: `dp[mask | bit(j)][j] = min(dp[mask | bit(j)][j], dp[mask][i] + travel[i][j])`. - Answer: `min over i of dp[full][i] + travel[i][depot]`, where `full` is the all-ones mask. Evaluation order is free: iterating masks in increasing numeric order works, because `mask` is numerically smaller than `mask | bit(j)` whenever bit j was clear. Every value is therefore final before it is read. ## What it costs | quantity | formula | n = 18 | |---|---|---| | states | 2^n · n | ≈ 4.7 million | | transitions | 2^n · n^2 | ≈ 85 million | | memory (4-byte entries) | 4 · 2^n · n | ≈ 19 MB | The extra dimension multiplies memory by n — real, but a *factor*, not another exponential. People sometimes fear it turns 2^n into something worse; it does not. ## Recovering the route The table holds costs, not orderings. Either store a parent index alongside each entry, or walk backwards at the end: from `(full, last)`, find the predecessor `i` in `mask` with `dp[mask without last][i] + travel[i][last] == dp[mask][last]`, then repeat. Reconstruction is O(n^2) at worst and costs nothing asymptotically. ## When the endpoint dimension is *not* needed The endpoint matters here only because the cost of a step depends on the previous choice. In problems where each step's cost depends only on *which* element is added and *how many* have been added — assigning workers to shifts, for instance — the extra dimension is redundant and should be dropped. Recognising which of the two shapes you are in is the actual skill; adding `last` reflexively wastes an n-fold factor, and omitting it when steps are coupled produces a confidently wrong answer. ## Common traps Forgetting the closing leg back to the depot; initialising unreached states to something other than infinity so garbage propagates; letting the mask include the depot and then wondering why the count is 2^(n+1); and assuming symmetry — with asymmetric travel times you cannot reverse a partial route and reuse its cost.
- Once the table is filled, how do you recover the actual visiting order?Either store a parent index with each entry, or reconstruct backwards: starting from the winning `(full, last)`, look for a predecessor `i` in the mask where `dp[mask without last][i] + travel[i][last]` equals `dp[mask][last]`, move to that state, and repeat until the mask is a single bit. Reconstruction is O(n^2) and does not change the complexity.
- Why not give the depot its own bit in the mask?It is fixed as both start and end, so it carries no decision. Giving it a bit doubles the table and creates masks that are unreachable or meaningless. Fixing the start also collapses the n rotations of the same closed tour into one representative, which is a genuine constant-factor win rather than just tidiness.
- Roughly what time and memory does 18 sites need?About 2^18 · 18 ≈ 4.7 million states, each with up to 18 outgoing transitions, so on the order of 85 million operations — comfortable. Memory is 4.7 million cost entries, roughly 19 MB at four bytes each, plus the same again if you store parent pointers. Both scale by two per extra site.
Knowing which errands you have already run does not tell you what the rest of the day costs — you also need to know which street corner you are standing on right now.
saying these in an interview costs you the question
- Says dp[mask] alone is enough because the set is the state
- Claims the state space is n! since orderings are being searched
- Thinks the second index makes the DP exponentially worse
- Forgets the closing leg back to the starting point
- Assumes travel costs are symmetric and reverses partial routes
- Leaves unreached states at zero instead of infinity