When dynamic programming is the wrong answer

The most common mistake after learning dynamic programming is using it everywhere. It is a specific tool for a specific shape, and three other tools beat it when they apply.

A greedy rule, when one can be justified

Fitting the most non-overlapping meetings into one room: take whichever finishes earliest, always. No table.

The justification is an exchange argument, and it is what separates a greedy rule that is provably right from one that merely looks sensible. Take any best possible schedule that does not start with the earliest-finishing meeting and swap its first meeting for that one: the replacement finishes no later, so nothing that followed can now clash, and the schedule is still valid and the same size.

If you cannot make that argument, do not trust the greedy rule. Coin change with arbitrary denominations is the standard warning: greedy gives 4 + 1 + 1 for a target of 6 with coins {1, 3, 4}, and 3 + 3 is better.

Divide and conquer, when the halves do not overlap

Merge sort and binary search split a problem and never revisit a piece. There is nothing to remember, so a memo would only waste memory.

A formula, when one exists

The number of paths across an empty grid is a binomial coefficient, in constant time. A table of ten thousand cells to compute something with a closed form is effort spent for nothing. Add obstacles and the formula breaks, and then the table earns its place.

And the bound is usually telling you

That last row is the one people miss. A capacity of a billion in a knapsack problem is not an invitation to build a bigger table, it is a signal that the intended solution is something else entirely.