Dynamic programming: basics

The idea

Solve each subproblem once and look it up after that

How many ways can you climb 5 steps, one or two at a time? Your last move was either one step, from step 4, or two, from step 3. So ways(5) = ways(4) + ways(3), and the same holds all the way down. That recurrence is correct, but as plain recursion it is slow: ways(5) calls ways(3), and so does ways(4). Each smaller count is computed again and again.

Dynamic programming fixes this. It applies when a problem has two properties:

overlapping subproblems: the recursion reaches the same smaller problem many times;
optimal substructure: the best (or total) answer for a problem is built from the answers of its subproblems, as ways(5) is built from ways(4) and ways(3).

There are two ways to use it. Memoization keeps the recursion and stores each answer in a memo the first time it is computed; later calls just read it. Tabulation drops the recursion and fills a table from the smallest subproblem up, so every value it needs is already there.

The rule

Say what one cell means ("best[i] is the most you can take from the first i + 1 houses"), write how a cell follows from smaller ones, and fill each cell once. The cost is the number of cells times the work per cell.

Spotting it

Counting ways, or the best way, over choices that repeat

"How many ways" to reach a total or the end

Add up the counts of the smaller cases you can come from

"Minimum" or "maximum" over a sequence of choices

Take the best over the last choice, using stored answers for the rest

A choice now changes what you may choose next (no two neighbors)

Carry the decision in the cell's meaning: best with or without item i

A recursive solution that times out on large inputs

Overlapping subproblems: add a memo, or turn it into a table

A greedy rule that a small counterexample breaks

Try every last choice with a table instead

Basic

Climbing stairs: a memo stops the repeated calls

The plain recursion for ways(n) makes a recursion tree that roughly doubles with every extra step. Counting its calls, including the ones that hit the base case:

Steps n	Calls without a memo	Calls with a memo
5	15	9
10	177	19
20	21,891	39
30	2,692,537	59
40	331,160,281	79

With a memo, each count from 2 to n is computed once and every later request for it is a lookup: 2n − 1 calls instead of an exponential number.

The memo is a list with a cell per step count. Filling the same list from cell 2 upward with a loop, no recursion at all, is tabulation, and that is what the next two examples do.

Medium

House robber: each cell chooses between two earlier cells

Houses in a row hold some money each, and you can't take from two neighbors. Let best[i] be the most you can take from houses 0 to i. For house i there are two choices: skip it and keep best[i − 1], or take it, which rules out house i − 1, for houses[i] + best[i − 2]. The cell keeps the larger.

Each cell reads only the two before it, so two variables could replace the list: O(n) time, O(1) space. That trimming is common once a table works.

Hard

Coin change: try every last coin

Find the fewest coins that add up to an amount. Taking the largest coin first fails for coins 1, 3 and 4 and amount 6. Instead, let dp[a] be the fewest coins for amount a. The last coin used was one of the coins c, so dp[a] = 1 + the smallest dp[a − c]. Fill dp from 1 up to the amount, trying every coin at every cell.

A starting value of amount + 1 stands for "not reachable yet": no real answer can use more coins than the amount itself. If the last cell still holds it, no combination works and the answer is −1. The cost is one cell per amount times one check per coin: O(amount × number of coins).

The template

Define the cell, the recurrence, the base and the order

1dp ← a table with one cell per subproblem
2set the base cases (the smallest subproblems)
3for each subproblem, smallest first
4 dp[cell] ← best (or total) over the last choice:
5 combine(dp[smaller cell], that choice)
6return dp[the whole problem]

Four decisions make every dynamic programming solution: what a cell means, how it follows from smaller cells, which cells are the base, and an order in which every cell's inputs are ready before it. With memoization the order comes for free, since the recursion asks for what it needs.

Traps

Where dynamic programming solutions go wrong

A vague cell

"dp[i] is the answer at i" is not enough. Say exactly what it holds: up to i or ending at i, with item i taken or not. Most wrong recurrences come from a fuzzy meaning.

Missing base cases

dp[0] and sometimes dp[1] must be set before the loop, and an impossible value needs a marker that can't be mistaken for an answer.

Filling in the wrong order

A cell must never read a cell that hasn't been filled yet.

A memo keyed on too little

If the answer depends on two things, such as an index and a remaining amount, the memo needs both in its key, or it returns answers for the wrong case.

Recursion too deep

Memoization on a large n can overflow the call stack; tabulation avoids that.

Check yourself

3 questions

1. Climbing stairs one or two steps at a time, how does ways(5) follow from smaller counts?

2. What is the difference between memoization and tabulation?

3. In coin change, why does every cell start at amount + 1?

Takeaways

Remember this

Dynamic programming applies when a recursion repeats subproblems and the answer is built from theirs: solve each once and look it up.
Memoization stores answers as the recursion finds them; tabulation fills a table from the smallest case up.
Say exactly what one cell means, how it follows from smaller cells, the base cases and the order; the cost is cells times the work per cell.

Practice

Now solve some yourself

Mixed with topics you have practiced 0 unlocked

1 more once you have practiced Hash tables & maps. Play one of its examples to the end and solve one of its problems to unlock them.

Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.