Dynamic Programming, Part 1: SRTBOT, Fib, DAGs, Bowling

MIT 6.006 Introduction to Algorithms, lecture 15, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part introduces dynamic programming as a way to design recursive algorithms, using a six-step checklist called SRTBOT and a first example with Fibonacci numbers.

Key ideas

Dynamic programming is a powerful way to design an algorithm by breaking a big problem into smaller versions of itself, which is a kind of recursive design. 0:57
SRTBOT is a memory aid for six steps: define the subproblems, write the relation between them, pick a topological order, give the base cases, solve the original problem, and analyze the running time. 2:25
Dynamic programming adds one idea to this template, memoization, which means reusing work you have already done instead of doing it again. 2:46
The hardest part is usually deciding what the subproblems should be, because the smaller pieces must be related to the problem you want to solve. 3:30
The subproblems must depend on each other in one direction only, with no loops. If they looped, the recursive calls would never stop. 4:56

Words to know

subproblem: A smaller version of the problem you are trying to solve, which you solve first so you can use its answer to build the bigger answer.
recurrence relation: A rule that says how to get the answer to one problem from the answers to smaller problems.
topological order: An order to solve the subproblems so that every subproblem is solved before any problem that depends on it. Think of it as a safe order to do the work.
memoization: Saving the answer to a piece of work the first time you do it, so you can reuse it later instead of repeating it.

Example

Imagine planning a long trip by working out the cost of each leg first, then using those costs to get the total. You never redo a leg you already priced, and you always price the small legs before the whole trip. That is the same idea as solving subproblems in order and reusing their answers.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part shows why the simple recursive way to compute Fibonacci numbers is too slow, and how remembering past answers (memoization) makes it fast.

Key ideas

The Fibonacci number f(i) is found by adding the two before it, and the algorithm computes the numbers in order from smallest to largest, so each smaller answer is ready before it is needed. 10:48
The plain recursive version recomputes the same smaller problems again and again, so its running time grows exponentially, which is very slow for large n. 13:22
Memoization means writing each answer down the first time you solve it, then looking it up instead of solving it again. This is the big idea of dynamic programming. 14:07
Before doing any work, the memoized code first checks whether the answer is already in the memo table. If it is, it returns that answer right away. 18:34
Because each subproblem is solved at most once, the total running time is just the number of subproblems times the small amount of work for each. For Fibonacci, that makes the time order n. 19:25

Words to know

Memoization: Writing down answers to smaller problems the first time you solve them, so you can look them up later instead of solving them again.
Subproblem: A smaller version of the main problem. Solving the smaller ones helps you solve the bigger one.
Base case: The simplest case, where the answer is already known and no further steps are needed.
Exponential growth: A quantity that multiplies by the same amount at each step, so it gets huge very fast. In algorithms, it means the work grows far too quickly as the input gets bigger.

Example

Imagine you are doing a long math homework set where many questions need the same intermediate answer. If you write that answer on a notepad the first time, you can just read it off the notepad every time after that, instead of working it out again.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part shows how saving answers you already computed (memoization) can turn a very slow recursive method into a fast one, using Fibonacci numbers, merge sort, and shortest paths in a graph as examples.

Key ideas

Plain recursion for Fibonacci takes exponential time, meaning the time grows far too fast. Saving each answer the first time you compute it (memoization) brings the time down to polynomial, which is much more manageable. 22:07
Fibonacci numbers get very large, so each addition takes about n over w steps, where w is the machine word size. Even so, the total work is n plus n squared over w, which is still polynomial. 21:22
With memoization, the total time is at most the sum, over all sub-problems, of the non-recursive work for each one. Recursive calls are not counted there, because they are counted as their own sub-problems. 23:15
Memoization does not help every recursive algorithm. Merge sort never repeats a sub-problem, so saving answers gains nothing there, though the same counting method still gives a polynomial upper bound. 24:47
A dynamic program is just recursion plus memoization. Each call first checks the memo table, returns the saved answer if there is one, handles base cases, and otherwise uses the recurrence and saves the result. 28:32

Words to know

memoization: Saving the answer to a problem the first time you solve it, so you can look it up instead of solving it again.
sub-problem: A smaller version of the main problem that you solve as one step on the way to the full answer.
exponential: A running time that grows so fast that each extra input roughly multiplies the work, so it gets huge quickly.
polynomial: A running time that grows like n raised to some fixed power, which grows much more slowly than exponential time.

Example

Imagine working out a long family tree, where you need the same grandparent's details many times. If you write each answer on a sticky note the first time and just read the note when you need it again, you avoid repeating the same work. That sticky-note habit is memoization.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part shows that a shortest-path problem on a directed graph with no cycles can be solved by writing one recursive rule and then computing answers in a safe order, and it introduces a bowling game with a product scoring rule.

Key ideas

To reach a vertex v, you must have come from one of the vertices that has an edge pointing into v. So the shortest path to v is the best of those choices, plus the edge weight. 30:21
A graph with no cycles has a topological order, which is a valid order to solve the smaller problems first. Because the graph has no cycles, such an order always exists. 31:30
The memo table is a record of answers already found, so the algorithm never repeats work. Running the recursion with that table is really a depth-first search, which produces the order for free. 34:22
Once the recursive rule is proven true, writing the algorithm is nearly effortless. The hard part is proving the rule, not coding the answer. 36:08
In the bowling game, hitting one pin i scores its value vi. Hitting two neighboring pins i and i+1 scores vi times vi+1, which is their product. 39:45

Words to know

topological order: A list of the vertices in a graph where each vertex comes before the ones it points to, so you can solve things in a safe order.
DAG: Directed acyclic graph: a set of points joined by one-way arrows, with no loop that ever brings you back to where you started.
memo table: A notebook where you write down each answer after you work it out, so you can look it up instead of working it out again.
relax: To check whether a new route to a point is shorter than the best one found so far, and if it is, to update the record with the shorter route.

Example

Think of a set of one-way roads that lead into a town. To find the quickest way to reach the town, you check each road that leads into it, add the travel time from where you started, and keep the shortest total. This matches the rule that the best path to v is the best of the paths coming into v.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part shows how to break a bowling scoring puzzle into smaller pieces, using suffixes of the pin line as the sub-problems, and how to write the rule that links them.

Key ideas

Each pin can be left alone or paired with a neighbor, but pairs cannot overlap, because a pin that has been knocked over is gone. Pairing two high-value pins can score much more than hitting them one at a time. 40:00
When the input is a sequence, useful sub-problems are prefixes (the start up to some point), suffixes (some point to the end), or substrings (a block in the middle). Each of these gives only polynomially many sub-problems. 43:03
Subsequences can skip items in the middle, so there are exponentially many of them. Using them as sub-problems would make the work too large, so the lesson avoids them. 44:31
When you write a dynamic program, first say what each sub-problem is trying to do. Here, b of i is the best score you can get from the pins starting at position i to the end. 46:26
To write the rule for b of i, look at pin i and list what you can do with it: skip it, hit it alone, or pair it with a pin. Each choice leaves a smaller suffix, and you take the maximum. 48:43

Words to know

suffix: The part of a list from some position to the very end. For example, the last three items of a list.
subsequence: A list made by picking items from the original in order, where you may skip items anywhere in the middle.
sub-problem: A smaller version of the main puzzle that you solve first, so you can use its answer to solve the bigger one.
recurrence relation: A rule that says how the answer to one sub-problem is worked out from the answers to smaller sub-problems.

Example

Imagine a line of people waiting for a bus, and you must decide what to do with each person in turn. If you only care about the people from the middle of the line to the back, you can solve that smaller line first, then add the front person's choice on top. This is like working with a suffix: cut off the front, solve the rest, and build the answer back up.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–57:10

This part shows how a bowling-pin scoring problem can be solved quickly by working through smaller leftover groups of pins, starting from the end and filling in answers as you go.

Key ideas

To decide what to do with the first pin, you only need to know the best score for the pins that remain. Those leftover pins form a smaller group, called a suffix. 50:00
Each smaller problem takes a fixed, small amount of work, and there are only a linear number of them. So the whole job takes linear time, which means the time grows in step with the number of pins. 50:42
The smaller problems must be solved in an order where each one's answers are ready before it is needed. Here, you start with the empty group at the end and work backward to the first pin. 51:30
You can write the same method as a simple for loop that fills in answers from the end back to the start. This avoids recursive calls and is usually faster in code. 52:14
The hard part is finding what you need to know to solve the problem. If the number of choices for that information is small (polynomial), the method works well. 56:46

Words to know

suffix: The part of a list that is left after you remove some items from the front. For example, pins 3 to 10 are a suffix of pins 1 to 10.
topological order: An order to solve smaller problems so that each one is solved before any problem that depends on it.
memoized: Saving the answer to a smaller problem the first time you compute it, so you can reuse it instead of working it out again.
local brute force: Trying every possible choice for one item, while reusing saved answers to the smaller problems that come after it, so the total work stays small.

Example

Imagine a line of coins, and you can take one coin or two neighboring coins, but you want the most total value. Ask yourself only one question at a time: what is the best you can do with the coins that remain after the first choice? Save those answers and build up from the end of the line, so each small answer is ready when you need it.

3 checked practice questions for this part are in the app.

← Lecture 13: Dijkstra · Lecture 16: Dynamic Programming, Part 2: LCS, LIS, Coins →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York