Which Technique Applies, and How to Tell

People who are good at this look like they are pattern-matching against problems they have seen. Mostly they are running a short procedure, quickly.

The procedure has three steps and one honest exit:

1. Write the brute-force recurrence. Check whether optimal solutions decompose into optimal sub-solutions.
2. Count the distinct states the recurrence reaches. Polynomial means dynamic programming applies.
3. Try to prove a greedy choice. Success is a large speedup; failure costs you a few minutes and usually hands you a counterexample.
4. If step 1 or step 2 fails, stop pretending. The problem may be intractable, and the useful question becomes which compromise to make.

What follows works through each step on real problems, then finishes with the cases where the textbook algorithm is not merely the best known but provably close to the best possible.

Notice the order. Greedy is attempted last, not first, even though it is the algorithm you would rather have.

That ordering is deliberate. Dynamic programming is the safe branch: it demands strictly less than greedy, so if greedy would have worked, DP works too. Starting from the recurrence means the fallback already exists before you gamble on a proof, and if the proof fails you have lost nothing.

Starting from greedy inverts the risk. You write ten correct-looking lines, test them on the examples in the problem statement, and ship a heuristic while believing you shipped an algorithm.

Write the exponential-time recursive solution first, even though you have no intention of running it. It does three jobs at once.

It exposes the state, because the arguments of the recursive function are the state, and you did not have to guess them.

It tests optimal substructure, because writing the recurrence forces you to say what the optimum decomposes into, and if the pieces interact you find out while writing rather than while debugging.

It gives you a reference implementation. The brute-force version is slow but obviously correct, so you can check the optimised version against it on small random inputs. That is the single most effective way to catch a state that is subtly too small, which otherwise produces wrong answers without any error.

Starting from the table instead means guessing the state, and a wrong guess is invisible until the results are wrong.

The state count decides whether dynamic programming is viable, and there are three regimes rather than two.

• Polynomial. Memoise and you are done. Prefix pairs give $O(nm)$, index plus capacity gives $O(nW)$.
• Exponential but structured. Subsets of a small set give $2^n$ states, which is disastrous asymptotically and often fine in practice. Held-Karp solves the travelling salesman with state (subset visited, current city) in $O(2^n n^2)$. At $n = 20$ that is about $4 \times 10^8$ operations against $20!$, roughly $2 \times 10^{18}$, for brute force. Ten orders of magnitude, and still exponential.
• Exponential and unstructured. The state is wrong, or the problem is genuinely hard.

A numeric field in the state deserves particular suspicion. It makes the count depend on a value rather than a length, which is where pseudo-polynomial running times come from.

Pick the most plausible rule and try an exchange argument. Assume an optimal solution that disagrees with your rule at its first choice, and try to swap your choice in without loss.

The attempt is cheap and it is informative either way. When it works you replace a table with a sort. When it fails, the obstruction you hit is usually a counterexample in disguise: the reason you cannot complete the swap is a concrete situation where the greedy choice costs something, and writing that situation down as an instance takes another minute.

There is one signal that reliably predicts failure. Greedy breaks when a local choice can strand a shared resource. If committing to the locally best item leaves behind capacity, time, or budget too small to be usable, the local decision cannot see the waste it caused, because the waste only becomes visible later.

Capacity 10. Three items as (weight, value): $(6, 12)$, $(5, 9)$, $(5, 9)$. Value-per-weight ratios are 2.0, 1.8 and 1.8, so ratio-greedy takes the first item.

items, capacity = [(6, 12), (5, 9), (5, 9)], 10

def greedy_by_ratio(items, capacity):
    total = 0
    for w, v in sorted(items, key=lambda it: it[1] / it[0], reverse=True):
        if w <= capacity:
            capacity -= w
            total += v
    return total

greedy_by_ratio(items, capacity)   # 12  -- takes (6,12), 4 capacity stranded
# optimum: (5,9) + (5,9) = 18, using all 10

Greedy is a third below optimal. Now allow fractions of items. The same rule takes all of item one, then four fifths of item two, for $12 + 7.2 = 19.2$, which is optimal.

Identical data. Adding divisibility means capacity can never be stranded, and the greedy rule goes from wrong to provably right.

Sometimes the procedure exits at step 1 or step 2 and the honest answer is that no efficient exact algorithm is coming. Four responses, roughly in order of what to try:

• Exponential DP anyway. Held-Karp is exponential and routinely used, because the input is small and $2^n n^2$ is not $n!$.
• Branch and bound. Search the tree but prune whenever a bound proves a subtree cannot beat the incumbent. Worst case unchanged, typical case often excellent.
• Approximate with a guarantee. Knapsack admits a fully polynomial-time approximation scheme: for any $\varepsilon > 0$ you can get within $1 - \varepsilon$ of optimal in time polynomial in $n$ and $1/\varepsilon$, by rounding values and running a value-indexed DP.
• Hand it to a solver. Express the problem as an integer program and let a mature solver apply decades of engineering you are not going to reproduce.

Noticing you are in this branch is itself the win. The failure mode is spending a week looking for a polynomial algorithm to an NP-hard problem.

A dynamic program that resists improvement can feel like a failure of imagination. Sometimes it is a theorem.

Edit distance has had the same $O(nm)$ algorithm since Wagner and Fischer published it in 1974. Backurs and Indyk showed at STOC in 2015 that this is essentially unavoidable: if edit distance could be computed in $O(n^{2-\delta})$ for any constant $\delta > 0$, then CNF satisfiability could be solved fast enough to refute the Strong Exponential Time Hypothesis.

Knapsack has a parallel story. Cygan and co-authors showed at ICALP in 2017 that knapsack variants are equivalent to $(\min,+)$-convolution, a problem with no known subquadratic algorithm, making Bellman's dynamic program conditionally near-optimal in the relevant regimes.

Both results are conditional on hardness hypotheses rather than unconditional. But they change what a failed optimisation means: not that you missed something, but that finding it would resolve a major open problem.

The value of this table is the third column. Memorising which technique goes with which problem is worth very little; the reasons transfer to problems that are not listed, and the pairings do not.