Dynamic Programming, Finally

Why dynamic programming does not click

Most introductions open with a table, fill it in, and announce the answer. You leave able to reproduce that table and unable to recognise the next problem that needs one.

The fix is to start from the condition that makes DP apply at all. Once you can see it in a problem, the table stops being a ritual and becomes the obvious thing to write.

The condition: the same subproblem, over and over

Dynamic programming pays off when a problem has overlapping subproblems — the same smaller question comes up many times along different paths.

Fibonacci is the standard demonstration. Computing fib(5) needs fib(4) and fib(3); fib(4) needs fib(3) again. The naive recursion recomputes the same values exponentially often, which is why it runs in O(2ⁿ). Remember each answer the first time you compute it and the same recursion runs in O(n).

That is the entire idea. Not recursion, not tables: each distinct state is computed exactly once.

If the subproblems never repeat, there is nothing to reuse, and plain divide and conquer is the right tool. Merge sort splits into halves that never overlap — no table would help it.

Top-down and bottom-up are the same algorithm

Memoisation is the recursion you would write anyway, with a cache in front of it. Tabulation is a loop that fills the same values in an order guaranteed to have the dependencies ready.

They compute identical answers with identical complexity. Memoisation only touches the states it actually needs and costs you stack depth; tabulation avoids recursion and is usually easier to optimise for memory. Choosing between them is a matter of taste far more often than people admit.

The hard part is the state, not the code

A state is the set of parameters that fully describes a subproblem — everything you need to know to answer it, and nothing else.

Get the state right and the transition usually writes itself. Get it wrong, and you will find yourself needing information the state does not carry, which is the real reason a DP solution refuses to come together.

For 0/1 knapsack the state is which items you have considered and how much capacity is left: dp[i][w] = max(dp[i−1][w], dp[i−1][w−wᵢ] + vᵢ). Both branches look at row i−1, which is exactly what stops an item being taken twice. Change the problem so items are unlimited and one index moves: the take branch looks at the current row instead, because after taking an item it is still available.

That one-index difference is the whole distinction between the two knapsacks, and it is worth being able to explain rather than memorise.

Where greedy quietly gives the wrong answer

Making change looks like a problem where taking the largest coin first must be optimal, and with everyday coin systems it is. With arbitrary denominations it is not.

Take coins of 1, 3 and 4, and a target of 6. Greedy takes 4, then 1, then 1 — three coins. The right answer is 3 + 3, two coins. Greedy never reconsiders, and that is precisely what DP does: dp[x] = 1 + min(dp[x − c]) over every coin c ≤ x considers all first moves instead of guessing one.

Reading the complexity honestly

The cost of a DP solution is the number of states multiplied by the cost of one transition. That single sentence answers most complexity questions about DP.

It also exposes a trap. Knapsack runs in O(nW), which looks polynomial and is not: W is a capacity value, and writing that value down takes only log W digits. Double the number of digits and the running time squares. This is called pseudo-polynomial time, and it is the reason knapsack is still considered hard.

One practical note while you are here: when a transition only ever reads the previous row, you do not need the whole table. Keeping one row cuts memory from O(nW) to O(W) and changes nothing else.