Dynamic Programming, Part 2: LCS, LIS, Coins

MIT 6.006 Introduction to Algorithms, lecture 16, 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 the longest common subsequence problem and shows how to set up its subproblems for two sequences at once.

Key ideas

The lesson names three new ideas: working with two sequences at once, working with substrings, and parent pointers to recover the actual answer. The longest common subsequence problem is the first example of these. 0:32
A subsequence is made by keeping some letters from a sequence in their original order and skipping others. A substring must be one unbroken piece. So the longest common subsequence of two inputs can have gaps in both. 4:58
With two input sequences, you choose a natural piece of each one, such as its suffix, and then pair every choice from the first with every choice from the second. The number of subproblems is the product of the two counts. 6:53
Each subproblem is a pair of suffixes, one from A and one from B. Including the empty suffix makes the base cases easy. 8:49
To write the relation, look at the first letter of each suffix. Removing that first letter leaves a smaller suffix, which gives a smaller subproblem. 9:36

Words to know

subsequence: A list of letters or items taken from a sequence in the same order, where you may skip some of them.
substring: One unbroken piece of a sequence, with no skipped letters.
memoize: Save the answer to each smaller problem the first time you solve it, so you never solve the same one twice.
topological order: An order to solve the subproblems so that every smaller problem is finished before any problem that depends on it.

Example

Think of the word hello hidden inside the longer words hieroglyphology and Michelangelo. You can find its letters in both words, in order, while skipping other letters in between. That is the idea of a subsequence: the letters keep their order, but gaps are allowed.

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

Part 2 · 10:00–20:00

This part shows how to find the longest shared sequence of letters in two words by comparing them one letter at a time, from the end toward the start.

Key ideas

When the first letters of the two strings are different, at least one of them cannot be in the shared sequence. We do not know which one, so we try both options and keep the longer result. 10:18
We try both options because we are trying to maximize the length of the shared sequence. We do not guess the right answer ahead of time. 10:39
When the first letters match, we can safely use that pair with no choice to make. We add one to the count and move on to the rest of both strings. 12:10
We fill in the answers starting with the empty suffixes, then build toward larger ones. Each small answer is ready before a bigger problem needs it. 14:21
There is one answer for every pair of starting positions, so the total work is the size of one string times the size of the other. For two strings of size n, that is n squared steps. 15:54

Words to know

subsequence: A list of letters taken in order from a longer string. The letters do not have to sit next to each other, but they must keep their original order.
suffix: The part of a string from some position to the end. For example, the suffix starting at position 2 is everything from position 2 onward.
subproblem: A smaller version of the original problem that we solve on the way to solving the big one. Here, each one asks for the answer on a pair of suffixes.
parent pointers: Arrows drawn from each answer back to the smaller answer it came from, so you can trace which choices built the final result.

Example

Imagine two friends each writing down a list of their favorite songs, and you want the longest run of songs that appear in both lists in the same order. At each step you compare the next song on each list: if they match, you keep it, and if not, you try skipping one list's song and then the other, and keep whichever path gives the longer shared list.

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

Part 3 · 20:00–30:00

This part shows how to get the actual answer, not just its length, from a dynamic programming table, and then sets up the longest increasing subsequence problem.

Key ideas

Once the table is filled in, you can trace the choices backward from the end. Each cell remembers which neighbor its max came from, and following those arrows (parent pointers) gives you the actual common subsequence, not only its length. 21:02
Fill the table in an order where every cell's helpers are already done. The lesson calls this topological order: work from right to left and bottom to top. 20:18
The longest increasing subsequence is the longest run of letters or numbers, taken in order, where each one is strictly bigger than the one before. You can skip items, but you cannot reorder them. 22:21
The first idea for a subproblem fails. It picks the current item and then assumes the rest will be increasing, but nothing forces that. The fix is to require the subsequence to start at the current item, so you know what the first item is and can compare it to the next one. 27:11
Changing the subproblem changes the question being answered. The answer to the original problem is no longer just the value at the start, but the best answer over all possible starting points. 29:24

Words to know

subsequence: A list you make by keeping some items from a sequence, in their original order, and dropping the others. You do not have to keep items next to each other.
suffix: The part of a sequence from some position to the end. For example, the suffix starting at position 3 is everything from position 3 onward.
parent pointers: Notes saved in each table cell that say which neighboring cell its best value came from. Following them backward retraces the best choices.
topological order: An order for doing the work so that every smaller piece is finished before any bigger piece that depends on it.

Example

Imagine picking a group of kids from a line so that their heights get taller each time, going from left to right. You can skip kids, but you cannot reorder them, and each pick must be strictly taller than the last. The task is to find the biggest group you can pick that way.

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

Part 4 · 30:00–40:00

This part shows how to find the longest increasing subsequence by asking, for each starting letter, what comes next, and trying every choice.

Key ideas

We don't know where the longest increasing subsequence starts, so we try every letter as a starting point and keep the biggest answer. 30:00
We define a smaller question, L(i): the longest increasing subsequence that must include letter i. The overall answer is the max of L(i) over all i. 30:29
To build L(i), we don't know the next letter j, so we try every j to the right of i. We only count j when the letter at j is bigger than the letter at i, and we add 1 for letter i itself. 31:34
We fill in answers from the end of the list backward, starting with the base case of an empty suffix, which is 0. With about n subproblems and about n choices each, the total work is about n squared. 35:25

Words to know

subproblem: A smaller version of the original problem that we solve on its way to the full answer.
brute force: Trying every possible choice instead of guessing or using a clever shortcut, so that you are sure to find the best one.
base case: The simplest starting answer that we know for sure, which the rest of the answers are built on.
strictly increasing: Each letter in the sequence must be bigger than the one before it, with no ties allowed.

Example

Imagine a line of people standing in a row, each with a height, and you want the longest group you can pick who get taller as they go. You try each person as the first pick, then for each one you check every person after them who is taller, and you keep the longest group you find.

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

Part 5 · 40:00–50:00

This part shows that some dynamic programming problems can also be solved as shortest path problems, and then works through a two-player coin game using substrings and whose turn it is.

Key ideas

A longest path problem can be turned into a shortest path problem by making every edge weight negative. The lecture does this with negative 1 on the edges. 40:00
Many dynamic programming problems can be drawn as a graph and solved with shortest paths. Writing a simple for loop and a recurrence is usually easier, because the order of the steps is already known. 41:46
In the coin game, you can take a coin from either end. Once coins are taken from both ends, the coins left form a middle chunk, so the subproblems must look at substrings, which are continuous pieces of the list. 45:30
The answer must also record whose turn it is, because after each move the turn passes to the other player. So the subproblem gets a third value that says who goes first. 48:03

Words to know

DAG: A directed acyclic graph: a set of dots joined by one-way arrows, with no loops that let you go around in a circle.
shortest path: The route between two points that adds up to the smallest total cost, such as the least distance or the lowest weight.
subproblem: A smaller version of the main problem that you solve first, so you can use its answer to solve the bigger one.
substring: A continuous piece taken from the middle or ends of a list, with no gaps.

Example

Picture a row of bread rolls on a table, and two friends take turns grabbing a roll from either end of the row. After a few grabs, the rolls left over form a single block in the middle, so you need to think about that middle block, not just the rolls at one end.

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

Part 6 · 50:00–58:36

This part explains how to write a recurrence (a step-by-step rule for solving a problem from smaller pieces) for a two-player coin game, where each player takes a coin from either end of a row.

Key ideas

Players take turns picking a coin from the left end or the right end of a row. Each choice shrinks the row, and then the other player moves. 50:00
The player choosing wants the most points, so you take the best of the two options. The opponent is trying to win too, so when it is their turn you assume they will pick the choice that is worst for you, which means using min. 52:30
The smallest problems are a single coin, which is the base case. The full game is solved by working from short rows up to the full row, so the total work is roughly n squared, which is quadratic. 53:35
Sometimes the problem flips whose turn it is, so you add a second set of subproblems that track the other player's turn. This doubles the number of subproblems but makes the rule much easier to write. 57:38

Words to know

subproblem: a smaller version of the original problem that you solve first, so you can use its answer to solve the bigger one.
zero-sum game: a game where whatever one player gains, the other player loses, so the two scores always add up to the same total.
recurrence relation: a rule that says how to find the answer to a problem from the answers to smaller problems.
parent pointers: arrows that record which choice gave the best answer at each step, so you can trace back the best strategy.

Example

Imagine two friends taking cookies from either end of a row, each wanting as many as possible. Once one friend takes a cookie, the other friend is the one to choose next, and they will try to take the best cookie for themselves. Thinking about what the other friend will do is what leads to using min in the rule.

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

← Lecture 15: Dynamic Programming, Part 1: SRTBOT, Fib, DAGs, Bowling

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