Dynamic programming

What it is

Dynamic programming solves a problem by expressing its answer in terms of the answers to smaller versions of itself, then filling those smaller answers in once — bottom-up in a table or top-down with memoization — instead of recomputing them on every branch of a recursion. The state is usually a small number of indices or a small remaining budget (a position in a string, a prefix of two strings, a remaining sum), and the payoff is turning an exponential number of possibilities into a table you can fill in polynomial time. Most solutions also collapse to O(1) or O(n) extra space once you notice the recurrence only reaches back one or two rows.

When it applies

• The problem asks for a count, a minimum/maximum, or a yes/no over all ways to build something, and a brute-force recursion would revisit the same subproblem many times.
• You can describe the answer for size n using the answer for strictly smaller sizes (one string prefix, one array index, one remaining amount), with a small, fixed number of choices at each step.
• Two sequences are being compared or merged position by position (edit distance, common subsequence, interleaving) — this is the classic 2D-table shape.
• If there's no overlap between subproblems at all (each subproblem is solved exactly once no matter what), you just have plain recursion or divide-and-conquer, not DP. If the choice at each step is always locally obvious and never needs to be reconsidered, reach for a greedy approach instead.

Tells in the problem

• "Return the number of ways to..." or "return the minimum/maximum number of operations/coins/steps to..."
• Adjacent-element restrictions like "no two chosen elements can be next to each other."
• Two strings or two sequences being transformed into or compared against each other.
• A target sum, capacity, or amount that many different subsets or combinations could reach.
• Small-looking recursive relations that a naive recursion would recompute exponentially (you can often confirm this by trying the brute-force recursion first and noticing it times out).

The classic mistake

The most common failure is writing the correct recurrence but re-deriving each subproblem from scratch with plain recursion, with no memo table and no bottom-up order — the code looks right on a tiny example and then blows up in time or hits recursion-depth limits on real input. This happens because the recurrence itself is genuinely the hard part to find, so once it's written it's tempting to treat the implementation as an afterthought. Catch it by asking, before you write a single line of code, "how many distinct subproblems exist, and in what order do I need their answers?" — if you can't answer that, you don't yet have a DP, you have a recursion.

Questions to start with

• Climbing Stairs — the smallest possible 1D recurrence; get the base cases and rolling-variable habit down before anything harder.
• House Robber — adds a real "take it or skip it" decision at each step, still with just two rolling values.
• Coin Change — introduces unbounded choices per step and the trap of assuming greedy works.
• Longest Common Subsequence — the template 2D DP over two sequences, and where the row-reduction trick becomes worth learning.
• Edit Distance — the same 2D shape with a three-way choice per cell, a good test of whether the recurrence habit has really stuck.