06 — NP-completeness and dynamic programming

The email's wording is the whole instruction: know the famous NP-complete classes and recognise them when an interviewer asks you them in disguise. Nobody will say "solve TSP". They will describe delivery routing and wait for you to name it.

Prereqs: 01, 09 · Reading: 7 min · Cards: 11

The map

Two topics that belong together because one is the escape hatch from the other. Recognising an NP-complete problem tells you not to look for a polynomial exact algorithm — but it is only half an answer, and stopping there scores a 1. The other half is knowing what to do instead, and the most common answer is dynamic programming, which turns many exponential recurrences into polynomial ones.

DP itself is not a bag of tricks. It is two questions asked in order: what is the state, and what is the transition? Every DP problem you will meet is a variation on defining those two things correctly, and saying them out loud before writing is what separates a candidate who understands DP from one who has memorised recurrences.

What decides your score here

Naming the problem, then asking about constraints. "This is the travelling salesman problem — it's NP-hard, so I don't expect an exact polynomial algorithm. What are the constraints?" That sentence changes the interview from "candidate is stuck" to "candidate is scoping".

Defining the state out loud before writing code. Half of DP failures are not algorithmic, they are candidates who started coding before they could say what dp[i][j] means.

Knowing why knapsack is still NP-complete despite the DP. It is the follow-up that separates memorised from understood, and it has a clean answer.

The classes, precisely

P is what you can solve in polynomial time. NP is what you can verify in polynomial time: given a candidate solution, checking it is fast. Every problem in P is also in NP — and the most common error on this topic is thinking NP means "not polynomial". It means nondeterministic polynomial.

NP-complete means both in NP and universal: every NP problem reduces to it. NP-hard means at least as hard as NP-complete, but not necessarily in NP itself.

That last distinction has a concrete instance worth having ready. The optimisation form of TSP — "what is the shortest route?" — is NP-hard, not NP-complete, because you cannot verify in polynomial time that a given route is the shortest. The decision form — "is there a route under k?" — is NP-complete, because verifying that is just adding up the edges. Making that distinction unprompted is the kind of precision that gets noticed.

The disguises

TSP arrives as routing deliveries and returning to the depot. Knapsack arrives as choosing items under a budget to maximise value. Subset sum arrives as "can this be split into two equal halves" or "assign plus and minus signs to reach a target". Bin packing arrives as placing jobs on servers. Graph colouring arrives as assigning time slots or frequencies without conflict. Vertex cover arrives as the smallest set of cameras covering every corridor.

The one pairing worth memorising is Euler versus Hamiltonian, because they sound identical and are not. A path using every edge once is Euler, is polynomial, and has a simple degree-based existence test. A path using every vertex once is Hamiltonian and is NP-complete. If a prompt says "visit each node exactly once", that is the hard one.

What to say once you have recognised it

Never "it's impossible". Name it, then ask about the constraints, because the constraints decide what you do — and there are four answers, in increasing order of compromise.

If n is small, twenty or fewer, an exact bitmask DP works: Held-Karp is O(2ⁿ·n²), which is entirely feasible at that size. If it must be exact but n is larger, branch and bound with good pruning is exponential in the worst case and fast in practice. If an approximation is acceptable, say the guarantee: the MST-based construction gives a 2-approximation for metric TSP, and Christofides gives 1.5. And if good enough is genuinely good enough, heuristics — simulated annealing, local search — get you there without any guarantee.

The point of listing four is that intractability is a statement about the asymptotic worst case, and real problems have bounds. Asking "what are the constraints?" is what demonstrates you know that.

Why knapsack is still NP-complete

Knapsack has a DP that runs in O(n·W), which looks polynomial. The resolution is that W enters the input written in log W bits — so as a function of the input size, that DP is exponential. It is called pseudo-polynomial: polynomial in the value, not in the size.

Being able to explain that is a genuinely senior-level answer, and it takes two sentences.

DP, as two questions

What is the state? What do I need to know in order to decide everything from here onward? For knapsack it is the item index and the remaining capacity. For edit distance it is the pair of prefixes.

What is the transition? How does the current state compose from earlier ones? For knapsack it is take-it-or-leave-it. For edit distance it is the three neighbouring cells, each corresponding to one edit operation.

Write it top-down with memoisation first. It maps directly onto the recurrence, it is easier to derive under pressure, and @functools.cache makes it one line. Convert to a bottom-up table only if there is time left or you need the space reduction.

The families are worth recognising by shape rather than memorising. One-dimensional state, dp[i], covers House Robber and longest increasing subsequence. Two-dimensional over two prefixes covers edit distance and longest common subsequence. Knapsack-shaped state — index plus a budget — covers coin change, subset sum and target sum. Interval state, dp[i][j] over a range, covers Burst Balloons. And bitmask state covers TSP for small n.

Two details that cost points. In a one-dimensional knapsack, the loop direction changes the problem: iterating capacity downwards gives 0/1 knapsack where each item is used once; upwards gives the unbounded version. And if each row depends only on the previous one, offer the space reduction at the end — "I can drop this from O(n·W) to O(W) since each row only depends on the previous" — which is a cheap way to end on a high note.

Say it

Cover the answers. Out loud, in English.

Now do this

Four problems that walk the DP families in order of difficulty.

1. House Robber — 15 min. One-dimensional state; say why greedy fails.
2. Coin Change — 25 min. Unbounded knapsack; give the counterexample that kills greedy.
3. Partition Equal Subset Sum — 25 min. Name it as subset sum before writing, and get the loop direction right.
4. Edit Distance — 30 min. The canonical 2D DP; name which operation each neighbour is.

Stop when you can state the state and transition out loud before coding, four times in a row.