I kept solving everything with dynamic programming

A confession to open a series with: for a long stretch, my answer to almost every algorithm problem was dynamic programming. Subproblems, a cache, a recurrence — it works on a huge range of problems, so it became the hammer. The solutions passed. They were also frequently overbuilt: I'd carry a whole table of state through a problem whose right answer was a single greedy pass or two pointers walking inward. I could produce the heavy solution and had no feel for the light one.

That's not a knowledge gap. It's a recognition gap — not knowing which tool the problem is asking for. And it turned out one question resolves most of it.

Do the choices interact?

Every one of these patterns is a sequence of decisions. The thing that decides which pattern you need is whether those decisions are entangled.

DP is what you reach for when you must remember where you've been. The moment you can prove you don't have to — that the greedy move now forecloses nothing — the table evaporates and a one-liner takes its place. Most of my overbuilt solutions were cases where the choices didn't actually interact and I'd assumed they did.

Don't hand me the rule — show me why it's safe

There's a second posture under this whole series, and it's the one that actually makes the patterns stick. When someone hands you "for this problem, move the shorter pointer" or "skip to the reset point," that's a recipe. Recipes don't transfer; the next problem looks different and the recipe doesn't fit. What transfers is the proof — the argument for why the cheap choice can't cost you later.

So every post here tries to bottom out in a mechanism, not a template:

• greedy bottoms out in the exchange argument — a way to prove the local choice is safe.
• sliding window bottoms out in a monotonicity prerequisite — the condition under which a window is even a legal tool.
• monotonic stack bottoms out in amortized O(n) accounting — each element pushed once, popped once.
• binary search on the answer bottoms out in a monotonic yes/no boundary — you're locating it, not building it.

The template, in each case, falls out of the reasoning by the end. It never opens the piece.

The series

Each post takes one pattern and derives it from the ground up — and, where it's honest, from the exact mistake I kept making while learning it.

• Greedy is easy to code and hard to justify — the keystone: the choices-interact test and the exchange argument.
• Sliding window: the prerequisite nobody mentions — monotonicity, the need-counter, record placement.
• Binary search has nothing to do with sorted arrays — searching a monotonic answer space.
• Prefix sum: turning a range query into a lookup — the tool I kept mis-reaching for with sliding window.
• Two pointers is a family, not a technique — converging vs read-write.
• Dynamic programming is recursion with a cache — state definition is the whole game.
• The monotonic stack is a waiting room — and why the leftovers aren't a bug.
• Carry history or start fresh: Kadane in one decision — and why sliding window can't do it.
• A heap is an array pretending to be a tree — index arithmetic and two repair operations.

Problems to practice