Dynamic Programming

Lesson 2 of 2 in Optimization · 60 min · Advanced

Remember answers to small problems; build the big one from them.

Introduction

How many different ways can you climb 10 stairs if every move is either 1 stair or 2 stairs?

Start listing them: ten 1-steps in a row, then eight 1-steps and one 2-step in every possible order, and so on. There are 89 routes in all, and each extra stair makes the list roughly 1.6 times longer. For 45 stairs the count passes 1.8 billion, so counting routes by hand is hopeless.

Now look only at the last move. You reached stair 10 either from stair 9 with a 1-step, or from stair 8 with a 2-step. Every route to stair 10 ends in one of those two ways.

Lesson overview

This lesson will show you how to:

Explain why a subproblem answer can be reused instead of recomputed.
Trace the stair-climbing table from 1 to 10 and read off 89.
Trace the grid-paths table, filling each cell from the cell above and left.
Choose the state to store, such as position or remaining amount.
Compare DP with greedy, which commits to one local choice.

The picture

dp, a grid of 4 rows by 5 columns. Row 0: 1, 1, 1, 1, 1. Row 1: 1, 2, 3, 4 (compare), 5. Row 2: 1, 3, 6 (compare), empty (focus), empty. Row 3: empty, empty, empty, empty, empty. Columns: 0, 1, 2, 3, 4. Dependencies: row 1, column 3 to row 2, column 3; row 2, column 2 to row 2, column 3.

Mental model

Think of a spreadsheet. Each cell holds a formula that reads a couple of cells above it or to its left, like =B2+C1. You fill the sheet from the top-left corner, and every cell is computed exactly once.

You never recompute a cell. You just read what is already there, and the answer you want is the last cell you fill.

Solve each small version of the problem once, write the answer in a table, and build every bigger answer by reading from the table.

Words to know

subproblem: A smaller version of the same question, like "how many ways to reach stair 7?" inside "how many ways to reach stair 10?".
overlapping subproblems: The same subproblem is needed again and again by different bigger ones. Stair 7 is needed by both stair 8 and stair 9. This is what makes a table worth building.
optimal substructure: The best answer to the big problem is made from the best answers to its subproblems. The fewest coins for 6 uses the fewest coins for a smaller amount.
state: The few numbers that name one subproblem: a stair number, a row and column, an amount. One table cell per state.
transition: The formula that builds one state from smaller ones, like dp[i] = dp[i − 1] + dp[i − 2] or the min over every coin.
base case: A state you can answer without the formula, like dp[0] = 1 (one way to stand still) or dp[0] = 0 (no coins make 0). Everything else is built on these.
memoization (top-down): Write the recursion as it reads, but cache each answer by state so it is computed only once.
tabulation (bottom-up): Skip the recursion. Fill a table from the base cases upward, in an order where every cell's inputs are already filled.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

Yes: The question asks "how many ways" or for the minimum or maximum cost, and brute force would try an exponential number of options.
Yes: The answer for a big input is built from answers to smaller inputs: stair n from n − 1 and n − 2, a cell from the cell above and the cell to its left.
Yes: A recursive solution would answer the same smaller question again and again.
Yes: What matters about the past is just a small state (a position, an amount, a length), not the whole path taken.

Not this when

No: A local choice is provably safe, like always attending the meeting that ends first: a sort and one pass beat a table. That is greedy.
No: You must list every solution (all subsets, all orderings), not count or optimise them: the output itself is exponential, so use recursion.
No: The subproblems never repeat, such as the fewest steps through a maze: a breadth-first search visits each place once, with nothing to reuse.

Which pattern fits?

Which pattern? 1 of 5
Count the distinct ways to climb n stairs when each move is 1 or 2 stairs.
Which pattern? 2 of 5
Given meetings with start and end times, attend as many non-overlapping meetings as possible.
Which pattern? 3 of 5
Return every subset of a list of distinct numbers.
Which pattern? 4 of 5
In a maze grid, find the fewest steps from the start to the exit, moving up, down, left or right.
Which pattern? 5 of 5
Find the fewest coins that make an amount, for any list of coin values, such as coins 1, 3 and 4 for amount 6.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode

1dp = a table of m rows × n columns
2dp[r][0] = 1 for every row, dp[0][c] = 1 for every column
for r from 1 to m − 1:
for c from 1 to n − 1:
3up = dp[r − 1][c]
3left = dp[r][c − 1]
4dp[r][c] = up + left
5return dp[m − 1][n − 1]

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def unique_paths(m, n):
    dp = [[0] * n for _ in range(m)]
    for r in range(m):
        dp[r][0] = 1
    for c in range(n):
        dp[0][c] = 1
    for r in range(1, m):
        for c in range(1, n):
            up = dp[r - 1][c]
            left = dp[r][c - 1]
            dp[r][c] = up + left
    return dp[m - 1][n - 1]

Time · O(m · n)Space · O(m · n)

A recipe that works for most problems: (1) say what one table cell means, (2) fill the base cases, (3) write the formula that builds a cell from smaller ones, (4) pick an order where a cell's inputs are already filled, (5) read the answer from the right cell.
Time is the number of states times the work per state. Here that is m · n cells at O(1) each. Coin change is amount × number of coins, because each amount tries every coin.
The full table is not always needed. Each row here reads only the row above it, so one row of length n is enough: O(n) space. Climbing stairs needs only the last two numbers: O(1). Rolling storage like this is optional, and it gives up the table you would need to rebuild the actual path.
Top-down (memoization) writes the same formula as a recursive function and caches by state. It has the same number of states, and computes only the states the answer actually needs, but recursion can run deep. The code in this lesson is bottom-up in every language.
If a cell reads a cell that is not filled yet, the answer is wrong, not slow. Check the order first: row by row, left to right works whenever cells read only up and left.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. Return the number of distinct ways to reach the top.

Input

n = 10

Output

Approach

The last move into stair i was a 1-step from i − 1 or a 2-step from i − 2, so dp[i] = dp[i − 1] + dp[i − 2].
Base cases: dp[0] = 1 (stand still) and dp[1] = 1 (one step).
Fill left to right: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. Each cell is written once and read at most twice more.
Only the last two cells are ever read, so two variables would also do, using O(1) space.

def climb_stairs(n):
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        one_step = dp[i - 1]
        two_steps = dp[i - 2]
        dp[i] = one_step + two_steps
    return dp[n]

Time · O(n)Space · O(n), or O(1) with two rolling variables

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

Plain recursion for stairs, ways(n) = ways(n − 1) + ways(n − 2), becomes very slow around n = 40. Why?
What is the difference between memoization and tabulation?
In Unique Paths, why is every cell in the first row and first column equal to 1?
Coins are 1, 3 and 4 and the amount is 6. Taking the biggest coin first gives 4 + 1 + 1 = 3 coins. What does the table method find?
Unique Paths fills an m × n table. What are its running time and the smallest memory you can get away with?

Question 1 of 5

Plain recursion for stairs, ways(n) = ways(n − 1) + ways(n − 2), becomes very slow around n = 40. Why?

It has to sort the stairs before it starts.It solves the same smaller stair counts over and over.The numbers get too big for the computer to add.Recursion is always slower than a loop.

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

Solve Min Cost Climbing Stairs (opens in a new tab) (LeetCode, easy)
Hint: The same shape as climbing stairs, but each cell holds a cost: the cheapest way to stand on step i comes from step i − 1 or i − 2.
Solve House Robber (opens in a new tab) (LeetCode, medium)
Hint: At each house either rob it (add the best from two houses back) or skip it (keep the best from the previous house), and keep the larger.
Solve Minimum Path Sum (opens in a new tab) (LeetCode, medium)
Hint: Unique Paths with costs: each cell adds its own cost to the smaller of the cell above and the cell to the left, instead of adding counts.
Solve Longest Increasing Subsequence (opens in a new tab) (LeetCode, medium)
Hint: Let dp[i] be the longest increasing subsequence that ends at index i, and look back at every earlier smaller number.
Solve Longest Common Subsequence (opens in a new tab) (LeetCode, medium)
Hint: A 2D table over prefixes of both strings: matching characters extend the diagonal cell, otherwise take the larger of up and left.
Solve Partition Equal Subset Sum (opens in a new tab) (LeetCode, medium)
Hint: Ask whether some subset adds up to half the total, with a table over sums where each number either joins the subset or doesn't.
Solve Edit Distance (opens in a new tab) (LeetCode, medium)
Hint: dp[i][j] is the cost of turning the first i letters into the first j; insert, delete and replace each read a different neighbour.
Solve Burst Balloons (opens in a new tab) (LeetCode, hard)
Hint: Think about the last balloon to burst in a range, not the first: then the two sides are independent subproblems.

Additional resources

Dynamic programming (Wikipedia) (opens in a new tab) — Overlapping subproblems and optimal substructure, with classic examples.
Longest common subsequence (Wikipedia) (opens in a new tab) — A classic two-dimensional table problem and a good next step after grid paths.
Knapsack problem (cp-algorithms) (opens in a new tab) — Table-based DP for choosing items under a limit, close in spirit to coin change.