DYNAMIC PROGRAMMING · FOUNDATION

Dynamic programming

Solve a big question by answering smaller versions of it once, saving each answer, and building on the saved answers.

Time O(n)Space O(n)10 practice problemsStep-through picture

The idea

Dynamic programming, or DP, is a way to solve a problem by splitting it into smaller problems of the same kind. You solve each small problem once, write its answer down, and reuse that answer whenever it is needed again. The big answer is built out of the small answers.

It fits when two things are true. First, the small problems overlap: the same small question comes up again and again. This is called overlapping subproblems. Second, the best answer to the big question can be made from the best answers to the small ones. This is called optimal substructure.

Every DP solution has three parts. The state is what one small question is about, such as "the number of ways to reach step i". The transition is the rule that builds one answer from smaller answers. The base case is the smallest question, whose answer you know without any work.

An everyday example

Counting routes up a staircase

You climb a staircase taking either one step or two steps at a time, and you want to know how many different ways there are to reach the top. To stand on step 5, your last move came from step 4 or from step 3. So the ways to reach step 5 are the ways to reach step 4 plus the ways to reach step 3. You write the count for each step on a sticky note as you go up, so you never count the routes to the same step twice.

How the example maps to the code
In the example	In the code
One sticky note per step	One cell of the `ways` array per step
The note on step 5 says how many routes end there	`ways[5]` is the number of ways to reach step 5
You arrive from one step below or two steps below	`ways[step] = ways[step - 1] + ways[step - 2]`
Standing at the bottom counts as one way	`ways[0] = 1`
Reading the note at the top	`return ways[n]`

From the slow way to dynamic programming

Start with the most direct way to count the ways up n steps: write a function that tries both possible first moves and adds up what each one leads to. The rule is count(n) = count(n - 1) + count(n - 2), with count(0) and count(1) equal to 1. It is short and it is correct.
Now count how much work it does. For n = 7 the function is called 41 times, even though there are only 8 different questions: step 0 to step 7. For n = 40 it is called 331,160,281 times. Each call makes two more calls, so the work roughly doubles every time n grows by one.
Look at where those calls go. In the run for n = 7, the question "how many ways to reach step 3?" is asked 5 times, and "step 1?" is asked 13 times. Every copy of the same question gets the same answer, because the answer depends only on the step number. All the repeated work is wasted.
So answer each question once and write the answer down. Keep an array ways, where ways[step] is the answer for step. When a question comes up again, read the array instead of working it out again. Now n = 40 needs 39 additions instead of 331 million calls.
One last idea removes the recursion too. Every answer only needs answers for smaller steps. So fill the array from the bottom: set the two base cells, then compute ways[2], ways[3], and so on, each from cells that are already filled. That loop is dynamic programming.

How it works

Define the state in words: what does one cell of your table answer? Here ways[step] is the number of ways to reach step.
Find the transition: how does the answer for one state come from smaller states? Ask "what was the last move?" Here the last move came from step - 1 or step - 2.
Find the base cases: the smallest states, known without any work. Here ways[0] = 1 and ways[1] = 1.
Pick an order so that every state's smaller states are already solved. Here that means going from step 2 up to step n.
Fill the table in that order, using the transition for each cell.
Read the final answer from the cell that matches the whole problem: ways[n].

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

function countWays(n) {
if (n <= 1) return 1;
const ways = new Array(n + 1).fill(0);
ways[0] = 1;
ways[1] = 1;
for (let step = 2; step <= n; step++) {
ways[step] = ways[step - 1] + ways[step - 2];
}
return ways[n];
}

How fast it is

Time	`O(n)`
Extra memory	`O(n)`

There is one cell for each step, and each cell is one addition. The table keeps n + 1 numbers. Since each cell only reads the two cells before it, two variables would be enough, which brings the space down to O(1).

Best caseO(1)
n is 0 or 1. Line 2 returns 1 before any table is made.
Average caseO(n)
Any n of 2 or more: the loop fills every cell from 2 to n once, with one addition each.
Worst caseO(n)
The same as the average. No input makes a cell cost more than one addition, and no cell is filled twice.

Common mistakes

Starting to code before writing the state in words. If you can't say what ways[i] means, the transition will be wrong. Write one sentence first.
Forgetting a base case, so the first loop reads a cell that was never set. Check which cells the first transition reads.
Filling the table in the wrong order, so a cell reads a neighbor that is still 0. Make sure every cell a transition reads is filled earlier.
Using plain recursion without saving answers. It gives the right answer for small inputs and freezes for n = 50. Save each answer.

When to use it

Look for these clues in a problem:

The question asks for a count ("how many ways"), a best value ("the least cost", "the most points"), or a yes or no ("is it possible").
You make a series of choices, and each choice leaves a smaller version of the same problem.
A plain recursive solution would ask the same smaller question many times.
Trying every combination would take far too long (for example 2^n choices for n = 50).

Check yourself

Answer each one in your head first, then open it.

Why is ways[0] set to 1 and not 0?

Because there is exactly one way to be at the bottom: make no moves. With 0 there, ways[2] would be 1 + 0 = 1 and miss the single two-step move.

How many additions does the loop make for n = 7?

Six, one for each step from 2 to 7. The plain recursive version makes 41 calls for the same n.

What two facts must be true for dynamic programming to help?

The same smaller questions must come up many times (overlapping subproblems), and the big answer must be buildable from the smaller answers (optimal substructure). Without the first, saving answers saves nothing.

What breaks if the loop runs from n down to 2?

Each cell would read cells that are still 0, because the smaller steps are filled later. The answers come out wrong with no error.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 10 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one promise: when it is about to fill ways[step], every cell from ways[0] to ways[step - 1] already holds the true number of ways to reach that step. The two base cells make this true before the loop starts.

Each step keeps the promise because of how the ways split up. Every way to reach step has a last move. Either it was a one-step move from step - 1, or a two-step move from step - 2. No way is in both groups, and no way is left out. The first group has exactly ways[step - 1] members and the second has ways[step - 2], so their sum is the true count. This is the optimal substructure from the intro, in its counting form: the big answer is built from the small answers with no loss.

The order of filling is what makes the reads safe. Every cell reads only smaller indexes, so going from left to right means the cells it reads are always done. The loop runs from 2 to n and then stops, so it ends after n - 1 additions, and the promise at that point says ways[n] is the answer.

Going deeper

4 more ideas

Why saving answers makes it fast

Without saving, counting the ways to reach step 40 asks for step 39 and step 38. Step 39 asks for step 38 again, and so on. The same questions are asked billions of times. With a table, each step is answered once, so there are only 40 additions.

How to find the recurrence

A recurrence is the transition written as a formula. To find one, look at the very last decision in a full solution. For the staircase, the last move was one step or two steps. Each choice leaves a smaller problem: reach step n - 1, or reach step n - 2. Combine those smaller answers: add them for a count, take the smallest for a cost, take the largest for a score, or use "or" for a yes or no.

How much work DP does

The work is the number of states times the work for each state. The staircase has n + 1 states and each needs one addition, so it takes O(n) time. A grid problem with rows * cols states that each look at two neighbors takes O(rows * cols) time.

Top-down or bottom-up

You can write DP in two styles. Memoization (top-down) writes the plain recursive solution and adds a cache, so each question is answered once. Tabulation (bottom-up) fills a table with a loop, smallest states first. Both give the same answers; the loop avoids deep recursion, and the recursion is often easier to write first.

Work it by hand

Every step in a table, with why

Count the ways to climb 7 steps, one or two steps at a time. Each row fills one cell of ways.

n = 7

Step	`step`	`ways[step - 1]`	`ways[step - 2]`	`ways[step]`	What happens	Why
1	0 and 1	-	-	1 and 1	Base cases set	`n` is more than 1, so the table is made. Reaching step 0 (doing nothing) and step 1 (one small move) each count as exactly one way.
2	2	1	1	2	`1 + 1`	The last move into step 2 came from step 1 or from step 0. Add the ways for both.
3	3	2	1	3	`2 + 1`	Both cells it reads were filled in earlier rows, so no recursion is needed.
4	4	3	2	5	`3 + 2`	Each new cell is one addition of the two cells just before it.
5	5	5	3	8	`5 + 3`	The plain recursive version would ask for step 3 again at this point. The table already has it.
6	6	8	5	13	`8 + 5`	The numbers grow fast: each is the sum of the two before it.
7	7	13	8	21	`13 + 8`, loop ends	`step` reaches `n`, the last cell is filled, and the loop stops. Line 9 returns `ways[7]`.

It returns 21 after 6 additions. The plain recursive version makes 41 calls for the same answer, and the gap grows quickly: 39 additions against 331 million calls for n = 40.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
Dynamic programming	`O(n)`	`O(n)`	The default: a short loop, no recursion, and the whole table is there if you want to look at it or rebuild a path.
Plain recursion	`O(2^n)`	`O(n)`	Only as a first draft to find the recurrence, or when `n` is tiny. It repeats the same questions millions of times.
Two rolling variables	`O(n)`	`O(1)`	When memory matters or `n` is in the millions, and you only need the final number.
Matrix power	`O(log n)`	`O(1)`	When `n` is huge, such as `10^18`, and the answer is asked modulo some number.

Extra memory: O(n) for the ways array of n + 1 numbers. Each cell only reads the two cells before it, so two variables are enough and the space drops to O(1).

How the steps grow

Dynamic programming, Two rolling variables O(n)
Plain recursion O(2^n)
Matrix power O(log n)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
Dynamic programming	10	1,000	1 million
Plain recursion	1,024	more than a quadrillion	more than a quadrillion
Two rolling variables	10	1,000	1 million
Matrix power	3	10	20

Inputs that need care

5 tricky inputs

n = 0: Line 2 returns 1. Standing still at the bottom counts as one way, which is also why ways[0] = 1 makes ways[2] come out right.
A negative n, such as -3: Line 2 also returns 1, which is not a meaningful answer. If the input can be negative, check it first and return 0 or throw an error.
A fraction, such as n = 3.5: new Array(4.5) throws a RangeError: Invalid array length. Check Number.isInteger(n) if the input comes from a user.
A large n, such as n = 78: ways[78] is 14,472,334,024,676,221, which is above Number.MAX_SAFE_INTEGER, so the last digits are wrong. Use BigInt, or return the answer modulo a number like 1_000_000_007 if the problem asks for that.
Some steps are broken and can't be stood on: Set ways[step] = 0 for a broken step instead of adding. Later cells then read 0 from it, so no way passes through it.

Variations and follow-ups

Twists interviewers add

Moves of one, two, or three steps

Each cell now reads three cells: ways[step] = ways[step - 1] + ways[step - 2] + ways[step - 3]. You need three base cells, or a check that skips negative indexes. With moves from 1 to k, keep a running sum of the last k cells so each cell is still one addition.

Moves from a list of allowed sizes

If the allowed moves are any sizes in a list, such as 1, 4, and 5, the cell adds ways[step - size] for every size that fits. This counts ordered sequences of moves, the same shape as the unbounded knapsack with the totals in the outer loop.

Cheapest climb instead of counting

When each step has a cost, change the addition into Math.min plus the cost. The table, the order, and the base cases keep the same shape. This is the tabulation template on its own page.

Very large `n` with matrix power

For n around 10^18, even O(n) is too slow. The pair (ways[step], ways[step - 1]) moves forward by multiplying with a fixed 2 by 2 matrix, so raising that matrix to the n-th power by repeated squaring gives the answer in O(log n) multiplications.

In an interview

Spot it, explain it, answer follow-ups

Spot it from the words "how many ways", "minimum cost", "maximum score", or "is it possible", together with choices that repeat: each step offers the same small set of moves.
Say the state as a sentence before coding: "ways[step] is the number of ways to reach step". Then say the last-move rule and the base cases. If you can't say the sentence, the table will be wrong.
Check the first few cells by hand: n = 0, 1, 2, and 3 should give 1, 1, 2, and 3. Listing the 3 ways for n = 3 (1+1+1, 1+2, 2+1) is a quick proof that the rule works.
Expect the follow-up "can you use less memory?". The answer is to keep only the last two values in two variables and shift them each step, which gives O(1) space.

Where frontend code uses it

The same idea in real UI code

React's useMemo and selector libraries such as Reselect save a computed value and reuse it until the inputs change. That is the same "answer once, reuse after" idea DP is built on.
Text diff views in code review tools are built on a DP table that compares every line of the old file with every line of the new one.
Spell checkers and "did you mean" hints compute an edit distance between words with a DP table.
Good line breaking for a paragraph, as in TeX's line breaker, picks every line break together with DP instead of filling each line greedily.

Dynamic programming

The idea

An everyday example

Counting routes up a staircase

From the slow way to dynamic programming

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why saving answers makes it fast

How to find the recurrence

How much work DP does

Top-down or bottom-up

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Moves of one, two, or three steps

Moves from a list of allowed sizes

Cheapest climb instead of counting

Very large `n` with matrix power

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

Counting routes up a staircase

From the slow way to dynamic programming

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why saving answers makes it fast

How to find the recurrence

How much work DP does

Top-down or bottom-up

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Moves of one, two, or three steps

Moves from a list of allowed sizes

Cheapest climb instead of counting

Very large n with matrix power

In an interview

Where frontend code uses it

Related algorithms

Very large `n` with matrix power