Dynamic Programming

Stop recomputing what you already worked out.

The idea

Dynamic programming applies when a problem has two properties: an optimal substructure (the best answer is built from best answers to smaller versions) and overlapping subproblems (those smaller versions recur). Without the second, plain recursion is already fine.

There are two ways to write the same thing:

Top-down — write the recursion, add a cache. Closest to how you reasoned about the problem, and it only computes the subproblems actually reached.
Bottom-up — fill a table from the smallest case upward. No recursion stack, and it often reveals that you only need the last row or two, which drops the space from O(n) to O(1).

The hard part is never the code. It is naming the state: what exactly does best[i] mean? Get that sentence precise and the recurrence is usually one line. Leave it vague and you will write a table you cannot debug.

Greedy is the tempting shortcut, and it fails on coin systems like [1, 3, 4] where making 6 greedily takes 4+1+1 instead of 3+3. DP considers the alternatives greedy discards.

Walkthrough

The table filling row by row. Each cell is the one above plus the one to its left — the recurrence, made visible. Watch the edges fill with 1s first, because there is exactly one way to walk a straight line.

What it costs

time: O(states × work per state)
space: O(states), often reducible to O(1) rows

The gain over naive recursion is usually exponential to polynomial, because a branching call tree collapses into one entry per distinct state.

When to reach for it

The problem asks for a maximum, minimum, or a count of ways.
You are making a sequence of choices where each affects what remains.
A recursive solution is obvious but recomputes the same arguments.
Greedy gives an answer that is wrong on a small counterexample.

Rather than the obvious alternative

Greedy

Far cheaper when it is correct. DP is what you fall back to when a locally best choice can block a globally best answer — a single counterexample decides which you are in.

Plain recursion

The same recurrence without memoisation. For a branching call tree the difference is exponential against polynomial, and it is one cache away.

Backtracking

Use backtracking when you need the arrangements themselves; DP when you only need the best value or a count, and the states repeat.

How to spot it

The problem asks for a maximum, minimum, or a count of ways.
You are making a sequence of choices where each affects what remains.
A recursive solution is obvious but recomputes the same arguments.
Greedy gives an answer that is wrong on a small counterexample.

Where it goes wrong

A vague state definition

If you cannot say in one sentence what `dp[i]` means, the recurrence will be wrong in a way that is very hard to see.

Wrong base cases

The table's first entries are the whole foundation. An off-by-one there is consistently wrong everywhere and looks like a logic bug.

Iterating in the wrong order

Bottom-up requires every dependency to be filled before it is read. Getting the loop order wrong reads zeroes and reports plausible nonsense.