# Edit Distance: From Memorization to Derivation > Dynamic programming taught as something you derive rather than something you recognise. Starting from two short words, sun and sand, the lecture states the subproblem in a single sentence, then asks the one question that produces a recurrence: what was the last edit? Each of delete, insert and substitute is argued from what it does to the two prefixes and drawn as an arrow from the neighbouring cell it comes from. The twenty cell table is then filled one square at a time, with three live arrows pointing into whichever square is being computed, so the dependence of a cell on its neighbours is watched rather than described. The same arrows are walked backwards to recover the actual sequence of edits, and the finished table is counted against the hundred and ninety three calls the naive recursion would have made on the same two words. - Canonical watch page: [Edit Distance: From Memorization to Derivation](https://academa.ai/lectures/edit-distance-dp-derivation) - Publisher: [Academa, Inc.](https://academa.ai) - Subject: Computer Science - Published: 2026-08-28T18:45:47.269Z - Updated: 2026-08-28T18:45:47.269Z - Duration: PT943S (15 minutes 43 seconds) - Chapters: 3 - Views: 0 - Language: en-US - Access: Free - Video stream: [HLS content](https://academa.ai/media/l/01M14TXCAC8KKYS97CWXZ1BWNE/0/dark/master.m3u8) - Audiovisual record: [Semantic JSON](https://academa.ai/media/l/01M14TXCAC8KKYS97CWXZ1BWNE/0/semantic.json) - Thumbnail: [Image](https://academa.ai/media/l/01M14TXCAC8KKYS97CWXZ1BWNE/0/dark/poster.jpg) ## Description Derive the edit distance recurrence, fill its table cell by cell, recover the edits, and count the work plain recursion repeats. ## Chapters - [00:00–04:11.243 · Two Words and the Edits Between Them](https://academa.ai/lectures/edit-distance-dp-derivation?t=0) - [04:11.243–07:41.032 · What the Last Step Was](https://academa.ai/lectures/edit-distance-dp-derivation?t=251.24268750000002) - [07:41.032–15:43 · Filling It In, and Reading It Back](https://academa.ai/lectures/edit-distance-dp-derivation?t=461.0323125) ## Transcript ### [00:00 · Two Words and the Edits Between Them](https://academa.ai/lectures/edit-distance-dp-derivation?t=0) Dynamic programming is usually taught as a list of solutions to memorise. I want to do the opposite. Over the next twenty minutes we are going to derive one, from a problem statement, with nothing remembered at all. The problem is edit distance, and what falls out of it is the method itself. So, two words. The source word is s u n, sun. The target word is s a n d, sand. You are allowed to change the source one character at a time until it reads like the target, and the question is how few changes that takes. Three moves are allowed, and only three. You can insert a character anywhere in the word. You can delete one. Or you can substitute one character for another, which is the only one of the three that leaves the length alone. Here is one way to get from one to the other. The s at the front already matches, so leave it alone. The u has to become an a, and that is one substitution. The n already matches too. And then there is a d hanging off the end of the target with nothing above it, so insert it. Look at the shape of that. Four columns, and the source only has three characters in it. That is exactly what an insertion is: a column with a target character in it and nothing standing above. Two edits in total, because two of the four columns cost nothing. Two is not obviously the smallest, though. Written out, that route is sun to san to sand. And here is a clumsier one: delete the u to get s n, insert an a, insert a d. Three edits, same destination. The edit distance is the minimum over every possible route, and there are a great many routes. Which means we are not going to enumerate them. We need to break the problem into smaller copies of itself, and that is the move that starts every dynamic program there is. Not a table. A sentence. Here is that sentence, and it is worth saying slowly. D of i and j is the edit distance between the first i characters of the source word and the first j characters of the target word. That is the entire definition. Prefixes, in other words. Not arbitrary pieces of the words, not suffixes, not substrings. Just: how much of each word have I dealt with so far? Sun has three characters and sand has four, so the answer to the original question is one single value. And choosing prefixes is a real choice, by the way. It is the choice that does all of the work here, and if you pick the wrong subproblem the rule will not close up on itself and you will have to come back and pick another one. Expect that to happen. Now suppose you code that definition up recursively, the obvious way. To compute D of three and four you try all three moves, and each one hands you back a smaller pair of prefixes to solve. Deleting gives you D of two, four. Inserting gives D of three, three. Substituting gives D of two, three. Three calls, every one of them strictly smaller than the thing we started with. Expand one more level and each of those three splits into three again. Nine calls, and we have only gone two deep. Now look carefully at what is actually written down there. D of two, three is here. And here. And again here. Three copies of one subproblem, and each copy is about to go off and compute the same number from scratch, knowing nothing whatsoever about the other two. That is the whole disease, and it is worth being precise about it. The recursion is correct. It is simply doing the same work over and over because it has no memory of what it has already worked out. Right at the end we will count exactly how much. So we have a subproblem. What we do not have yet is the rule that ties one subproblem to the smaller ones, and that rule comes out of a single question about the last character. ### [04:11.243 · What the Last Step Was](https://academa.ai/lectures/edit-distance-dp-derivation?t=251.24268750000002) The rule always comes out of the same question, whatever the problem happens to be. Look at the very end of both prefixes, and ask what the last step was. These four squares are a corner of the table we are about to build. The one at the bottom right is the cell we want, D of i and j. The other three are all strictly smaller subproblems: one row up, one column to the left, and one of each. Suppose the last edit deleted the source character A sub i. Then that character is gone, it was matched against nothing at all, and what is left over is the first i minus one characters of the source against the whole first j of the target. That is the cell directly above, plus one for the deletion itself. Suppose instead that the last edit inserted the target character B sub j. Now the source is untouched, and it is the target that has one fewer character left to account for. That is the cell immediately to the left, plus one for the insertion. And the third possibility is that A sub i and B sub j were simply lined up against each other. Both prefixes lose a character, so we arrive from the diagonal. What that step costs depends entirely on the two characters. That case is worth pausing on, because it is doing two jobs at once. When the two characters already agree, it is a match and it costs nothing at all. When they disagree, it is a substitution and it costs one. Same arrow, same neighbour, two different prices. Make that concrete. Take i equals two and j equals two, so the prefixes are s u and s a. The last characters are u and a. They are different, so that diagonal step costs one, sitting on top of whatever the distance between s and s turned out to be. Call that extra cost c. Zero when the two characters agree, one when they do not. That single letter is the only place the actual words enter the arithmetic. Everything else in the rule is pure bookkeeping. Three cases, three neighbours, and no fourth possibility anywhere. Any edit sequence at all has to end in one of those three, so the cheapest sequence ends in whichever of the three is cheapest. So there is the recurrence, and notice that we did not guess it and we did not remember it. It is nothing more than the minimum over the three ways the last step could have gone. Read it as a picture rather than as algebra. One plus the cell above. One plus the cell to the left. Or c plus the cell on the diagonal. Take whichever of those three is smallest, and that is your answer. And here is the cost, spelled out properly. c is zero if the character at position i and the character at position j are the same, and one if they are not. There is a hole in this, though. Every one of those three cases points at a smaller cell, which is perfectly fine right up until the moment there is no smaller cell to point at. The recurrence cannot start itself. So we also need the cases that are true with no recursion at all. Those turn out to be the easy part, because a prefix of length zero is just the empty word. And that is where the table finally comes in. ### [07:41.032 · Filling It In, and Reading It Back](https://academa.ai/lectures/edit-distance-dp-derivation?t=461.0323125) Here is the table. Four rows, because sun has three characters and we need a row for zero characters as well. Five columns, for the same reason, with sand. Every single square in it is one subproblem. The square in row i and column j is going to hold D of i and j, and the one we actually want is down there in the bottom right corner. Start with row zero. That row is the source prefix of length zero, which is the empty word. Turning the empty word into the first j characters of sand costs exactly j insertions, one per character, so row zero simply counts up. Zero, one, two, three, four. Column zero is the mirror image of that. Turning the first i characters of sun into the empty word costs i deletions, so it counts down the side. One, two, three. Those eight squares are true by definition rather than by any rule. And look at the corner one: no characters against no characters, nothing to do, zero. Everything else comes from the rule we derived, and the three ways in keep the three colours from before: red from above, blue from the left, yellow from the diagonal. Twelve squares left, and each one is the smallest of three numbers already sitting on the page. Take the first empty one, row one, column one. Row one means the source prefix is s. Column one means the target prefix is s. Three arrows point into that square, one from each neighbour, and the square holds the smallest of what those three arrows offer. From above, the neighbour holds one, and a deletion costs one more, so two. From the left, one again, plus one for an insertion, so two again. From the diagonal, zero, and both characters here are s, so c is zero and the diagonal asks for nothing extra. Zero wins, so the square is zero, and that is exactly right. Turning s into s costs nothing at all. Now slide the arrows one column to the right. Row one is still just s. Column two is s a. From above, three. From the left, one. From the diagonal, one, and this time the characters are s and a, which differ, so add one and you get two. The smallest is one. One insertion. Build s a out of a single s by adding an a on the end. The table just derived that on its own, and it will keep doing it. The rest of that row goes the same way. Column three, two. Column four, three. Row one now reads one, zero, one, two, three, and each of those is the cost of building a longer and longer prefix of sand out of one s. Row two now, so the source prefix is s u. Back to column one, where the target is s. From above, zero plus one is one. From the left, two plus one is three. From the diagonal, one plus one is two, because u and s are different. One wins. And notice which arrow it came from. The one from above, the red one, which is a deletion. Turning s u into s means throwing the u away, and the table found that by itself. This next one is the interesting square. Row two, column two: s u against s a. From above, two. From the left, two. From the diagonal, zero plus one, because u and a differ. One, from the diagonal, and that diagonal step is exactly the substitution we spotted by eye at the very start. Finish the row. Column three gives two. Column four gives three. Nothing matches anywhere along there, so every step is costing something. Last row, so the source is the whole word, s u n. Column one gives two. Column two gives two as well. Column three is worth slowing down for. Source s u n, target s a n. The last characters are both n, so c is zero, and the diagonal offers one plus nothing. Above offers three, the left offers three, the diagonal offers one. The number drops. That is a free match paying for itself. And now the very last square. Source s u n, target s a n d. The last characters are n and d, which differ. Above gives four. The diagonal gives three. And from the left, one plus one is two. Two. That is the edit distance between sun and sand, and every one of those twenty numbers was worked out exactly once, from numbers already sitting above it and to its left. Now the number on its own is not really the interesting part. The table also knows which moves it used to get there, and we can read them back out by walking the winning arrows backwards from the corner. Start at the bottom right. The two there came from the left neighbour, which held one. A step from the left is an insertion, so the last edit was inserting the d. From that square, the one came from the diagonal, and the characters there were n and n, equal, so the step cost nothing. A free diagonal step is a match. Keep the n exactly as it is. From there, the one came from the diagonal again, but this time u and a were different, so the step cost one. That is a substitution. And the last diagonal step is another free match, s against s, and it lands us back in the empty corner. Four steps, one for each column of the alignment we drew at the very beginning. Read that path forwards and you have the script. Match the s at the front. Substitute the u with an a. Match the n in the middle. Insert a d at the end. Two of those four steps are free, and the two that cost anything add up to two, which is the number sitting in the corner. So the table did not merely measure the distance. It constructed the edits. So what did all of that buy us? Twenty squares. Twenty subproblems, each one solved exactly once and then written down where the others can see it. The plain recursion from earlier, run to completion on these same two short words, makes a hundred and ninety three calls. Same answer, nearly ten times the work, and the extra nine tenths of it is the same handful of subproblems being recomputed. And it gets worse very fast. Take kitten and sitting, which is the standard example. The table has fifty six squares in it. The recursion makes nearly thirty thousand calls. The table is m plus one times n plus one, always, no matter what the words are. The recursion is exponential in the length of the words. That gap is the whole of what dynamic programming buys you, and it is bought with a grid you could draw on a napkin. And notice that nothing in that argument was about spelling. Strip the two words out of it and what is left is a procedure. Name the subproblem in one sentence. If you cannot say it in one sentence you do not have it yet, and no amount of staring at a table will rescue you. Ask what the last decision could have been. Not the first one, the last one, because the last one is what leaves a smaller version of the same problem behind it. Then let each answer point at that smaller version. Write down the cases the rule cannot reach, which are almost always the empty ones. And then fill the thing in in an order where everything a square needs is already there. For us that was left to right and top to bottom, because every arrow pointed up or left. Five steps, and not one of them mentioned edit distance. The next time you meet one of these, do not go looking for the solution you memorised. Go and find the sentence. ## About Academa, Inc. Academa makes technical knowledge easier to understand through visual lectures and lets learners request new lecture videos on the topics they need. ## Complete audiovisual record Immutable source: [semantic.json](https://academa.ai/media/l/01M14TXCAC8KKYS97CWXZ1BWNE/0/semantic.json) Record version: 1. Render attempt: 0. ### How to read this timeline Each scene owns its object identifiers. A beat's board is the complete board when listed, empty when marked empty, and unchanged from the nearest earlier listed board in the same scene when marked unchanged. Action times are absolute positions in the published video. ### Scene 1: [Two Words and the Edits Between Them](https://academa.ai/lectures/edit-distance-dp-derivation?t=0) Span: 00:00–04:11.243 (0s–251.24268750000002s). #### Objects - add\_d: a Vector \[blue\] drawn in words (start=(3.5, 1.9), end=(3.5, 0.65)) - caption: a Text \[text\] that says "The same subproblem, three times, two levels down." - card: a Title that says "Algorithms — Edit Distance: From Memorization to Derivation" - chain\_bad: a Math \[text\] that says "$upright("sun") arrow.r upright("sn") arrow.r upright("san") arrow.r upright("sand")$" - chain\_good: a Math \[text\] that says "$upright("sun") arrow.r upright("san") arrow.r upright("sand")$" - edge\_a: a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(2.2, 1.8)) - edge\_a1: a Line \[gray\] drawn in tree (start=(2.2, 1.8), end=(1.0, 0.4)) - edge\_a2: a Line \[gray\] drawn in tree (start=(2.2, 1.8), end=(2.2, 0.4)) - edge\_a3: a Line \[gray\] drawn in tree (start=(2.2, 1.8), end=(3.4, 0.4)) - edge\_b: a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(6.0, 1.8)) - edge\_b1: a Line \[gray\] drawn in tree (start=(6.0, 1.8), end=(4.8, 0.4)) - edge\_b2: a Line \[gray\] drawn in tree (start=(6.0, 1.8), end=(6.0, 0.4)) - edge\_b3: a Line \[gray\] drawn in tree (start=(6.0, 1.8), end=(7.2, 0.4)) - edge\_c: a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(9.8, 1.8)) - edge\_c1: a Line \[gray\] drawn in tree (start=(9.8, 1.8), end=(8.6, 0.4)) - edge\_c2: a Line \[gray\] drawn in tree (start=(9.8, 1.8), end=(9.8, 0.4)) - edge\_c3: a Line \[gray\] drawn in tree (start=(9.8, 1.8), end=(11.0, 0.4)) - goal\_math: a Math \[text\] that says "$D(3, 4) quad upright("is the answer")$" - head\_ops: a Heading that says "Three Ways to Change a Word" - head\_sub: a Heading that says "The Subproblem, in One Sentence" - head\_tree: a Heading that says "What Plain Recursion Does" - keep\_n: a Line \[gray\] drawn in words (start=(2.5, 2.0), end=(2.5, 0.6)) - keep\_s: a Line \[gray\] drawn in words (start=(0.5, 2.0), end=(0.5, 0.6)) - kid\_a1: a Point \[text\] labelled "D(1, 4)" drawn in tree (location=(1.0, 0.4), marker\_radius=0.09) - kid\_a2: a Point \[text\] labelled "D(2, 3)" drawn in tree (location=(2.2, 0.4), marker\_radius=0.09) - kid\_a3: a Point \[text\] labelled "D(1, 3)" drawn in tree (location=(3.4, 0.4), marker\_radius=0.09) - kid\_b1: a Point \[text\] labelled "D(2, 3)" drawn in tree (location=(4.8, 0.4), marker\_radius=0.09) - kid\_b2: a Point \[text\] labelled "D(3, 2)" drawn in tree (location=(6.0, 0.4), marker\_radius=0.09) - kid\_b3: a Point \[text\] labelled "D(2, 2)" drawn in tree (location=(7.2, 0.4), marker\_radius=0.09) - kid\_c1: a Point \[text\] labelled "D(1, 3)" drawn in tree (location=(8.6, 0.4), marker\_radius=0.09) - kid\_c2: a Point \[text\] labelled "D(2, 2)" drawn in tree (location=(9.8, 0.4), marker\_radius=0.09) - kid\_c3: a Point \[text\] labelled "D(1, 2)" drawn in tree (location=(11.0, 0.4), marker\_radius=0.09) - lvl\_a: a Point \[text\] labelled "D(2, 4)" drawn in tree (location=(2.2, 1.8), marker\_radius=0.09) - lvl\_b: a Point \[text\] labelled "D(3, 3)" drawn in tree (location=(6.0, 1.8), marker\_radius=0.09) - lvl\_c: a Point \[text\] labelled "D(2, 3)" drawn in tree (location=(9.8, 1.8), marker\_radius=0.09) - ops: a Block \[text\] that says "Insert one character. Delete one character. Substitute one character for another." - point: a Point \[yellow\] drawn in words (location=(1.5, 2.3)) - root: a Point \[text\] labelled "D(3, 4)" drawn in tree (location=(6.0, 3.2), marker\_radius=0.09) - src\_n: a Math \[text\] that says "$upright("n")$" drawn in words - src\_s: a Math \[text\] that says "$upright("s")$" drawn in words - src\_u: a Math \[text\] that says "$upright("u")$" drawn in words - sub\_def: a Panel that says "$D(i, j)$ is the edit distance between the first $i$ characters of the source word and the first $j$ characters of the target word." - swap\_u: a Line \[yellow\] drawn in words (start=(1.5, 2.0), end=(1.5, 0.6)) - tgt\_a: a Math \[text\] that says "$upright("a")$" drawn in words - tgt\_d: a Math \[text\] that says "$upright("d")$" drawn in words - tgt\_n: a Math \[text\] that says "$upright("n")$" drawn in words - tgt\_s: a Math \[text\] that says "$upright("s")$" drawn in words - tree: a Figure (x\_range=(0.2, 11.8), y\_range=(-0.5, 3.8), aspect=(11.6, 4.3)) - words: a Figure (x\_range=(-0.6, 4.6), y\_range=(-0.4, 2.8), aspect=(5.2, 3.2)) #### Beats ##### [00:00](https://academa.ai/lectures/edit-distance-dp-derivation?t=0) Narration: Dynamic programming is usually taught as a list of solutions to memorise. I want to do the opposite. Over the next twenty minutes we are going to derive one, from a problem statement, with nothing remembered at all. The problem is edit distance, and what falls out of it is the method itself. Board: Empty. Actions: - [00:00](https://academa.ai/lectures/edit-distance-dp-derivation?t=0): card is shown on the screen, written out. - [00:1.5](https://academa.ai/lectures/edit-distance-dp-derivation?t=1.5): card: enter:write-left-to-right. - [00:16.057](https://academa.ai/lectures/edit-distance-dp-derivation?t=16.057): card is hidden from the screen — left the board. ##### [00:17.257](https://academa.ai/lectures/edit-distance-dp-derivation?t=17.256999999999998) Narration: So, two words. The source word is s u n, sun. The target word is s a n d, sand. You are allowed to change the source one character at a time until it reads like the target, and the question is how few changes that takes. Board: Unchanged from the preceding beat in this scene. Actions: - [00:17.257](https://academa.ai/lectures/edit-distance-dp-derivation?t=17.256999999999998): words is shown on the screen, written out. - [00:19.753](https://academa.ai/lectures/edit-distance-dp-derivation?t=19.753): src\_s is shown on the screen, written out. - [00:19.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=19.893): src\_u is shown on the screen, written out. - [00:20.033](https://academa.ai/lectures/edit-distance-dp-derivation?t=20.033): src\_n is shown on the screen, written out. - [00:23.039](https://academa.ai/lectures/edit-distance-dp-derivation?t=23.038999999999998): tgt\_s is shown on the screen, written out. - [00:23.179](https://academa.ai/lectures/edit-distance-dp-derivation?t=23.179): tgt\_a is shown on the screen, written out. - [00:23.319](https://academa.ai/lectures/edit-distance-dp-derivation?t=23.319): tgt\_n is shown on the screen, written out. - [00:23.459](https://academa.ai/lectures/edit-distance-dp-derivation?t=23.459): tgt\_d is shown on the screen, written out. ##### [00:35.422](https://academa.ai/lectures/edit-distance-dp-derivation?t=35.4225) Narration: Three moves are allowed, and only three. You can insert a character anywhere in the word. You can delete one. Or you can substitute one character for another, which is the only one of the three that leaves the length alone. Board: words — a Figure (x\_range=(-0.6, 4.6), y\_range=(-0.4, 2.8), aspect=(5.2, 3.2)); src\_s — a Math \[text\] that says "$upright("s")$" drawn in words; src\_u — a Math \[text\] that says "$upright("u")$" drawn in words; src\_n — a Math \[text\] that says "$upright("n")$" drawn in words; tgt\_s — a Math \[text\] that says "$upright("s")$" drawn in words; tgt\_a — a Math \[text\] that says "$upright("a")$" drawn in words; tgt\_n — a Math \[text\] that says "$upright("n")$" drawn in words; tgt\_d — a Math \[text\] that says "$upright("d")$" drawn in words Actions: - [00:35.771](https://academa.ai/lectures/edit-distance-dp-derivation?t=35.771): words moves to a new place on the board. - [00:35.771](https://academa.ai/lectures/edit-distance-dp-derivation?t=35.771): ops is shown on the screen, written out. - [00:38.696](https://academa.ai/lectures/edit-distance-dp-derivation?t=38.696): ops (the "Insert" part) is emphasized. - [00:41.297](https://academa.ai/lectures/edit-distance-dp-derivation?t=41.297): point is shown on the screen, grown. - [00:41.297](https://academa.ai/lectures/edit-distance-dp-derivation?t=41.297): ops (the "Delete" part) is emphasized. - [00:41.297](https://academa.ai/lectures/edit-distance-dp-derivation?t=41.297): ops (the "Insert" part) is no longer emphasized. - [00:42.806](https://academa.ai/lectures/edit-distance-dp-derivation?t=42.806): ops (the "Delete" part) is no longer emphasized. - [00:42.806](https://academa.ai/lectures/edit-distance-dp-derivation?t=42.806): ops (the "Substitute" part) is emphasized. - [00:43.497](https://academa.ai/lectures/edit-distance-dp-derivation?t=43.497): point is hidden from the screen. - [00:47.59](https://academa.ai/lectures/edit-distance-dp-derivation?t=47.5895): ops (the "Substitute" part) is no longer emphasized. ##### [00:48.189](https://academa.ai/lectures/edit-distance-dp-derivation?t=48.189499999999995) Narration: Here is one way to get from one to the other. The s at the front already matches, so leave it alone. The u has to become an a, and that is one substitution. The n already matches too. And then there is a d hanging off the end of the target with nothing above it, so insert it. Board: ops — a Block \[text\] that says "Insert one character. Delete one character. Substitute one character for another."; words — a Figure (x\_range=(-0.6, 4.6), y\_range=(-0.4, 2.8), aspect=(5.2, 3.2)); src\_s — a Math \[text\] that says "$upright("s")$" drawn in words; src\_u — a Math \[text\] that says "$upright("u")$" drawn in words; src\_n — a Math \[text\] that says "$upright("n")$" drawn in words; tgt\_s — a Math \[text\] that says "$upright("s")$" drawn in words; tgt\_a — a Math \[text\] that says "$upright("a")$" drawn in words; tgt\_n — a Math \[text\] that says "$upright("n")$" drawn in words; tgt\_d — a Math \[text\] that says "$upright("d")$" drawn in words Actions: - [00:52.38](https://academa.ai/lectures/edit-distance-dp-derivation?t=52.379999999999995): keep\_s is shown on the screen, written out. - [00:57.222](https://academa.ai/lectures/edit-distance-dp-derivation?t=57.222): swap\_u is shown on the screen, written out. - [00:59.079](https://academa.ai/lectures/edit-distance-dp-derivation?t=59.079): keep\_n is shown on the screen, written out. - [01:4.698](https://academa.ai/lectures/edit-distance-dp-derivation?t=64.69800000000001): add\_d is shown on the screen, written out. ##### [01:6.332](https://academa.ai/lectures/edit-distance-dp-derivation?t=66.3315) Narration: Look at the shape of that. Four columns, and the source only has three characters in it. That is exactly what an insertion is: a column with a target character in it and nothing standing above. Two edits in total, because two of the four columns cost nothing. Board: ops — a Block \[text\] that says "Insert one character. Delete one character. Substitute one character for another."; words — a Figure (x\_range=(-0.6, 4.6), y\_range=(-0.4, 2.8), aspect=(5.2, 3.2)); src\_s — a Math \[text\] that says "$upright("s")$" drawn in words; src\_u — a Math \[text\] that says "$upright("u")$" drawn in words; src\_n — a Math \[text\] that says "$upright("n")$" drawn in words; tgt\_s — a Math \[text\] that says "$upright("s")$" drawn in words; tgt\_a — a Math \[text\] that says "$upright("a")$" drawn in words; tgt\_n — a Math \[text\] that says "$upright("n")$" drawn in words; tgt\_d — a Math \[text\] that says "$upright("d")$" drawn in words; keep\_s — a Line \[gray\] drawn in words (start=(0.5, 2.0), end=(0.5, 0.6)); swap\_u — a Line \[yellow\] drawn in words (start=(1.5, 2.0), end=(1.5, 0.6)); keep\_n — a Line \[gray\] drawn in words (start=(2.5, 2.0), end=(2.5, 0.6)); add\_d — a Vector \[blue\] drawn in words (start=(3.5, 1.9), end=(3.5, 0.65)) Actions: - [01:13.867](https://academa.ai/lectures/edit-distance-dp-derivation?t=73.86700000000002): add\_d is indicated — a transient flash. - [01:22.434](https://academa.ai/lectures/edit-distance-dp-derivation?t=82.434): keep\_s is indicated — a transient flash. - [01:22.434](https://academa.ai/lectures/edit-distance-dp-derivation?t=82.434): keep\_n is indicated — a transient flash. ##### [01:23.847](https://academa.ai/lectures/edit-distance-dp-derivation?t=83.84700000000001) Narration: Two is not obviously the smallest, though. Written out, that route is sun to san to sand. And here is a clumsier one: delete the u to get s n, insert an a, insert a d. Three edits, same destination. The edit distance is the minimum over every possible route, and there are a great many routes. Board: Unchanged from the preceding beat in this scene. Actions: - [01:28.178](https://academa.ai/lectures/edit-distance-dp-derivation?t=88.17800000000001): chain\_good is shown on the screen, written out. - [01:31.393](https://academa.ai/lectures/edit-distance-dp-derivation?t=91.393): chain\_bad is shown on the screen, written out. - [01:38.104](https://academa.ai/lectures/edit-distance-dp-derivation?t=98.104): chain\_bad is indicated — a transient flash. - [01:42.214](https://academa.ai/lectures/edit-distance-dp-derivation?t=102.214): chain\_good is indicated — a transient flash. ##### [01:47.121](https://academa.ai/lectures/edit-distance-dp-derivation?t=107.12100000000001) Narration: Which means we are not going to enumerate them. We need to break the problem into smaller copies of itself, and that is the move that starts every dynamic program there is. Not a table. A sentence. Board: ops — a Block \[text\] that says "Insert one character. Delete one character. Substitute one character for another."; chain\_good — a Math \[text\] that says "$upright("sun") arrow.r upright("san") arrow.r upright("sand")$"; chain\_bad — a Math \[text\] that says "$upright("sun") arrow.r upright("sn") arrow.r upright("san") arrow.r upright("sand")$"; words — a Figure (x\_range=(-0.6, 4.6), y\_range=(-0.4, 2.8), aspect=(5.2, 3.2)); src\_s — a Math \[text\] that says "$upright("s")$" drawn in words; src\_u — a Math \[text\] that says "$upright("u")$" drawn in words; src\_n — a Math \[text\] that says "$upright("n")$" drawn in words; tgt\_s — a Math \[text\] that says "$upright("s")$" drawn in words; tgt\_a — a Math \[text\] that says "$upright("a")$" drawn in words; tgt\_n — a Math \[text\] that says "$upright("n")$" drawn in words; tgt\_d — a Math \[text\] that says "$upright("d")$" drawn in words; keep\_s — a Line \[gray\] drawn in words (start=(0.5, 2.0), end=(0.5, 0.6)); swap\_u — a Line \[yellow\] drawn in words (start=(1.5, 2.0), end=(1.5, 0.6)); keep\_n — a Line \[gray\] drawn in words (start=(2.5, 2.0), end=(2.5, 0.6)); add\_d — a Vector \[blue\] drawn in words (start=(3.5, 1.9), end=(3.5, 0.65)) Actions: - [01:52.148](https://academa.ai/lectures/edit-distance-dp-derivation?t=112.148): swap\_u is indicated — a transient flash. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): chain\_bad is hidden from the screen — left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): chain\_good is hidden from the screen — left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): ops is hidden from the screen — left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): words is hidden from the screen — left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): src\_s is hidden from the screen — words left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): src\_u is hidden from the screen — words left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): src\_n is hidden from the screen — words left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): tgt\_s is hidden from the screen — words left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): tgt\_a is hidden from the screen — words left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): tgt\_n is hidden from the screen — words left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): tgt\_d is hidden from the screen — words left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): keep\_s is hidden from the screen — words left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): swap\_u is hidden from the screen — words left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): keep\_n is hidden from the screen — words left the board. - [01:59.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=119.89250000000001): add\_d is hidden from the screen — words left the board. ##### [02:1.093](https://academa.ai/lectures/edit-distance-dp-derivation?t=121.0925) Narration: Here is that sentence, and it is worth saying slowly. D of i and j is the edit distance between the first i characters of the source word and the first j characters of the target word. That is the entire definition. Board: Empty. Actions: - [02:1.093](https://academa.ai/lectures/edit-distance-dp-derivation?t=121.0925): head\_sub is shown on the screen, written out. - [02:2.009](https://academa.ai/lectures/edit-distance-dp-derivation?t=122.009): sub\_def is shown on the screen, written out. - [02:6.294](https://academa.ai/lectures/edit-distance-dp-derivation?t=126.294): sub\_def (the "edit distance" part) is emphasized. - [02:13.91](https://academa.ai/lectures/edit-distance-dp-derivation?t=133.91): sub\_def (the "edit distance" part) is no longer emphasized. ##### [02:15.636](https://academa.ai/lectures/edit-distance-dp-derivation?t=135.636) Narration: Prefixes, in other words. Not arbitrary pieces of the words, not suffixes, not substrings. Just: how much of each word have I dealt with so far? Sun has three characters and sand has four, so the answer to the original question is one single value. Board: sub\_def — a Panel that says "$D(i, j)$ is the edit distance between the first $i$ characters of the source word and the first $j$ characters of the target word."; head\_sub — a Heading that says "The Subproblem, in One Sentence" Actions: - [02:31.948](https://academa.ai/lectures/edit-distance-dp-derivation?t=151.94799999999998): goal\_math is shown on the screen, written out. ##### [02:33.686](https://academa.ai/lectures/edit-distance-dp-derivation?t=153.686) Narration: And choosing prefixes is a real choice, by the way. It is the choice that does all of the work here, and if you pick the wrong subproblem the rule will not close up on itself and you will have to come back and pick another one. Expect that to happen. Board: sub\_def — a Panel that says "$D(i, j)$ is the edit distance between the first $i$ characters of the source word and the first $j$ characters of the target word."; goal\_math — a Math \[text\] that says "$D(3, 4) quad upright("is the answer")$"; head\_sub — a Heading that says "The Subproblem, in One Sentence" Actions: - [02:35.834](https://academa.ai/lectures/edit-distance-dp-derivation?t=155.83399999999997): sub\_def (the "characters of the source word" part) is indicated — a transient flash. - [02:48.361](https://academa.ai/lectures/edit-distance-dp-derivation?t=168.36100000000002): goal\_math is hidden from the screen — left the board. - [02:48.361](https://academa.ai/lectures/edit-distance-dp-derivation?t=168.36100000000002): head\_sub is hidden from the screen — left the board. - [02:48.361](https://academa.ai/lectures/edit-distance-dp-derivation?t=168.36100000000002): sub\_def is hidden from the screen — left the board. ##### [02:49.561](https://academa.ai/lectures/edit-distance-dp-derivation?t=169.561) Narration: Now suppose you code that definition up recursively, the obvious way. To compute D of three and four you try all three moves, and each one hands you back a smaller pair of prefixes to solve. Board: Empty. Actions: - [02:49.561](https://academa.ai/lectures/edit-distance-dp-derivation?t=169.561): head\_tree is shown on the screen, written out. - [02:49.561](https://academa.ai/lectures/edit-distance-dp-derivation?t=169.561): tree is shown on the screen, written out. - [02:54.658](https://academa.ai/lectures/edit-distance-dp-derivation?t=174.658): root is shown on the screen, written out. - [02:57.363](https://academa.ai/lectures/edit-distance-dp-derivation?t=177.363): edge\_a is shown on the screen, drawn. - [02:57.463](https://academa.ai/lectures/edit-distance-dp-derivation?t=177.463): edge\_b is shown on the screen, drawn. - [02:57.563](https://academa.ai/lectures/edit-distance-dp-derivation?t=177.563): edge\_c is shown on the screen, drawn. - [02:59.465](https://academa.ai/lectures/edit-distance-dp-derivation?t=179.465): lvl\_a is shown on the screen, written out. - [02:59.585](https://academa.ai/lectures/edit-distance-dp-derivation?t=179.585): lvl\_b is shown on the screen, written out. - [02:59.705](https://academa.ai/lectures/edit-distance-dp-derivation?t=179.705): lvl\_c is shown on the screen, written out. ##### [03:2.364](https://academa.ai/lectures/edit-distance-dp-derivation?t=182.36350000000002) Narration: Deleting gives you D of two, four. Inserting gives D of three, three. Substituting gives D of two, three. Three calls, every one of them strictly smaller than the thing we started with. Board: tree — a Figure (x\_range=(0.2, 11.8), y\_range=(-0.5, 3.8), aspect=(11.6, 4.3)); head\_tree — a Heading that says "What Plain Recursion Does"; root — a Point \[text\] labelled "D(3, 4)" drawn in tree (location=(6.0, 3.2), marker\_radius=0.09); edge\_a — a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(2.2, 1.8)); edge\_b — a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(6.0, 1.8)); edge\_c — a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(9.8, 1.8)); lvl\_a — a Point \[text\] labelled "D(2, 4)" drawn in tree (location=(2.2, 1.8), marker\_radius=0.09); lvl\_b — a Point \[text\] labelled "D(3, 3)" drawn in tree (location=(6.0, 1.8), marker\_radius=0.09); lvl\_c — a Point \[text\] labelled "D(2, 3)" drawn in tree (location=(9.8, 1.8), marker\_radius=0.09) Actions: - [03:2.665](https://academa.ai/lectures/edit-distance-dp-derivation?t=182.665): lvl\_a is emphasized. - [03:5.765](https://academa.ai/lectures/edit-distance-dp-derivation?t=185.765): lvl\_a is no longer emphasized. - [03:5.765](https://academa.ai/lectures/edit-distance-dp-derivation?t=185.765): lvl\_b is emphasized. - [03:8.494](https://academa.ai/lectures/edit-distance-dp-derivation?t=188.49399999999997): lvl\_b is no longer emphasized. - [03:8.494](https://academa.ai/lectures/edit-distance-dp-derivation?t=188.49399999999997): lvl\_c is emphasized. - [03:12.429](https://academa.ai/lectures/edit-distance-dp-derivation?t=192.42899999999997): lvl\_c is no longer emphasized. ##### [03:17.012](https://academa.ai/lectures/edit-distance-dp-derivation?t=197.0115) Narration: Expand one more level and each of those three splits into three again. Nine calls, and we have only gone two deep. Board: Unchanged from the preceding beat in this scene. Actions: - [03:19.647](https://academa.ai/lectures/edit-distance-dp-derivation?t=199.647): edge\_a1 is shown on the screen, drawn. - [03:19.717](https://academa.ai/lectures/edit-distance-dp-derivation?t=199.71699999999998): edge\_a2 is shown on the screen, drawn. - [03:19.787](https://academa.ai/lectures/edit-distance-dp-derivation?t=199.78699999999998): edge\_a3 is shown on the screen, drawn. - [03:19.857](https://academa.ai/lectures/edit-distance-dp-derivation?t=199.85699999999997): edge\_b1 is shown on the screen, drawn. - [03:19.927](https://academa.ai/lectures/edit-distance-dp-derivation?t=199.92699999999996): edge\_b2 is shown on the screen, drawn. - [03:19.997](https://academa.ai/lectures/edit-distance-dp-derivation?t=199.99699999999996): edge\_b3 is shown on the screen, drawn. - [03:20.067](https://academa.ai/lectures/edit-distance-dp-derivation?t=200.06699999999995): edge\_c1 is shown on the screen, drawn. - [03:20.137](https://academa.ai/lectures/edit-distance-dp-derivation?t=200.13699999999994): edge\_c2 is shown on the screen, drawn. - [03:20.207](https://academa.ai/lectures/edit-distance-dp-derivation?t=200.20699999999994): edge\_c3 is shown on the screen, drawn. - [03:21.667](https://academa.ai/lectures/edit-distance-dp-derivation?t=201.66699999999997): kid\_a1 is shown on the screen, written out. - [03:21.757](https://academa.ai/lectures/edit-distance-dp-derivation?t=201.75699999999998): kid\_a2 is shown on the screen, written out. - [03:21.847](https://academa.ai/lectures/edit-distance-dp-derivation?t=201.84699999999998): kid\_a3 is shown on the screen, written out. - [03:21.937](https://academa.ai/lectures/edit-distance-dp-derivation?t=201.93699999999998): kid\_b1 is shown on the screen, written out. - [03:22.027](https://academa.ai/lectures/edit-distance-dp-derivation?t=202.027): kid\_b2 is shown on the screen, written out. - [03:22.117](https://academa.ai/lectures/edit-distance-dp-derivation?t=202.117): kid\_b3 is shown on the screen, written out. - [03:22.207](https://academa.ai/lectures/edit-distance-dp-derivation?t=202.207): kid\_c1 is shown on the screen, written out. - [03:22.297](https://academa.ai/lectures/edit-distance-dp-derivation?t=202.297): kid\_c2 is shown on the screen, written out. - [03:22.387](https://academa.ai/lectures/edit-distance-dp-derivation?t=202.387): kid\_c3 is shown on the screen, written out. ##### [03:25.019](https://academa.ai/lectures/edit-distance-dp-derivation?t=205.019) Narration: Now look carefully at what is actually written down there. D of two, three is here. And here. And again here. Three copies of one subproblem, and each copy is about to go off and compute the same number from scratch, knowing nothing whatsoever about the other two. Board: tree — a Figure (x\_range=(0.2, 11.8), y\_range=(-0.5, 3.8), aspect=(11.6, 4.3)); head\_tree — a Heading that says "What Plain Recursion Does"; root — a Point \[text\] labelled "D(3, 4)" drawn in tree (location=(6.0, 3.2), marker\_radius=0.09); edge\_a — a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(2.2, 1.8)); edge\_b — a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(6.0, 1.8)); edge\_c — a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(9.8, 1.8)); lvl\_a — a Point \[text\] labelled "D(2, 4)" drawn in tree (location=(2.2, 1.8), marker\_radius=0.09); lvl\_b — a Point \[text\] labelled "D(3, 3)" drawn in tree (location=(6.0, 1.8), marker\_radius=0.09); lvl\_c — a Point \[text\] labelled "D(2, 3)" drawn in tree (location=(9.8, 1.8), marker\_radius=0.09); edge\_a1 — a Line \[gray\] drawn in tree (start=(2.2, 1.8), end=(1.0, 0.4)); edge\_a2 — a Line \[gray\] drawn in tree (start=(2.2, 1.8), end=(2.2, 0.4)); edge\_a3 — a Line \[gray\] drawn in tree (start=(2.2, 1.8), end=(3.4, 0.4)); edge\_b1 — a Line \[gray\] drawn in tree (start=(6.0, 1.8), end=(4.8, 0.4)); edge\_b2 — a Line \[gray\] drawn in tree (start=(6.0, 1.8), end=(6.0, 0.4)); edge\_b3 — a Line \[gray\] drawn in tree (start=(6.0, 1.8), end=(7.2, 0.4)); edge\_c1 — a Line \[gray\] drawn in tree (start=(9.8, 1.8), end=(8.6, 0.4)); edge\_c2 — a Line \[gray\] drawn in tree (start=(9.8, 1.8), end=(9.8, 0.4)); edge\_c3 — a Line \[gray\] drawn in tree (start=(9.8, 1.8), end=(11.0, 0.4)); kid\_a1 — a Point \[text\] labelled "D(1, 4)" drawn in tree (location=(1.0, 0.4), marker\_radius=0.09); kid\_a2 — a Point \[text\] labelled "D(2, 3)" drawn in tree (location=(2.2, 0.4), marker\_radius=0.09); kid\_a3 — a Point \[text\] labelled "D(1, 3)" drawn in tree (location=(3.4, 0.4), marker\_radius=0.09); kid\_b1 — a Point \[text\] labelled "D(2, 3)" drawn in tree (location=(4.8, 0.4), marker\_radius=0.09); kid\_b2 — a Point \[text\] labelled "D(3, 2)" drawn in tree (location=(6.0, 0.4), marker\_radius=0.09); kid\_b3 — a Point \[text\] labelled "D(2, 2)" drawn in tree (location=(7.2, 0.4), marker\_radius=0.09); kid\_c1 — a Point \[text\] labelled "D(1, 3)" drawn in tree (location=(8.6, 0.4), marker\_radius=0.09); kid\_c2 — a Point \[text\] labelled "D(2, 2)" drawn in tree (location=(9.8, 0.4), marker\_radius=0.09); kid\_c3 — a Point \[text\] labelled "D(1, 2)" drawn in tree (location=(11.0, 0.4), marker\_radius=0.09) Actions: - [03:30.336](https://academa.ai/lectures/edit-distance-dp-derivation?t=210.33599999999998): lvl\_c is emphasized. - [03:31.428](https://academa.ai/lectures/edit-distance-dp-derivation?t=211.42799999999997): kid\_a2 is emphasized. - [03:32.821](https://academa.ai/lectures/edit-distance-dp-derivation?t=212.82099999999997): kid\_b1 is emphasized. ##### [03:43.069](https://academa.ai/lectures/edit-distance-dp-derivation?t=223.0685) Narration: That is the whole disease, and it is worth being precise about it. The recursion is correct. It is simply doing the same work over and over because it has no memory of what it has already worked out. Right at the end we will count exactly how much. Board: Unchanged from the preceding beat in this scene. Actions: - [03:48.676](https://academa.ai/lectures/edit-distance-dp-derivation?t=228.67599999999996): lvl\_c is no longer emphasized. - [03:48.676](https://academa.ai/lectures/edit-distance-dp-derivation?t=228.67599999999996): kid\_a2 is no longer emphasized. - [03:48.676](https://academa.ai/lectures/edit-distance-dp-derivation?t=228.67599999999996): kid\_b1 is no longer emphasized. - [03:53.053](https://academa.ai/lectures/edit-distance-dp-derivation?t=233.05299999999997): caption is shown on the screen, written out. ##### [03:58.994](https://academa.ai/lectures/edit-distance-dp-derivation?t=238.9935) Narration: So we have a subproblem. What we do not have yet is the rule that ties one subproblem to the smaller ones, and that rule comes out of a single question about the last character. Board: tree — a Figure (x\_range=(0.2, 11.8), y\_range=(-0.5, 3.8), aspect=(11.6, 4.3)); caption — a Text \[text\] that says "The same subproblem, three times, two levels down."; head\_tree — a Heading that says "What Plain Recursion Does"; root — a Point \[text\] labelled "D(3, 4)" drawn in tree (location=(6.0, 3.2), marker\_radius=0.09); edge\_a — a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(2.2, 1.8)); edge\_b — a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(6.0, 1.8)); edge\_c — a Line \[gray\] drawn in tree (start=(6.0, 3.2), end=(9.8, 1.8)); lvl\_a — a Point \[text\] labelled "D(2, 4)" drawn in tree (location=(2.2, 1.8), marker\_radius=0.09); lvl\_b — a Point \[text\] labelled "D(3, 3)" drawn in tree (location=(6.0, 1.8), marker\_radius=0.09); lvl\_c — a Point \[text\] labelled "D(2, 3)" drawn in tree (location=(9.8, 1.8), marker\_radius=0.09); edge\_a1 — a Line \[gray\] drawn in tree (start=(2.2, 1.8), end=(1.0, 0.4)); edge\_a2 — a Line \[gray\] drawn in tree (start=(2.2, 1.8), end=(2.2, 0.4)); edge\_a3 — a Line \[gray\] drawn in tree (start=(2.2, 1.8), end=(3.4, 0.4)); edge\_b1 — a Line \[gray\] drawn in tree (start=(6.0, 1.8), end=(4.8, 0.4)); edge\_b2 — a Line \[gray\] drawn in tree (start=(6.0, 1.8), end=(6.0, 0.4)); edge\_b3 — a Line \[gray\] drawn in tree (start=(6.0, 1.8), end=(7.2, 0.4)); edge\_c1 — a Line \[gray\] drawn in tree (start=(9.8, 1.8), end=(8.6, 0.4)); edge\_c2 — a Line \[gray\] drawn in tree (start=(9.8, 1.8), end=(9.8, 0.4)); edge\_c3 — a Line \[gray\] drawn in tree (start=(9.8, 1.8), end=(11.0, 0.4)); kid\_a1 — a Point \[text\] labelled "D(1, 4)" drawn in tree (location=(1.0, 0.4), marker\_radius=0.09); kid\_a2 — a Point \[text\] labelled "D(2, 3)" drawn in tree (location=(2.2, 0.4), marker\_radius=0.09); kid\_a3 — a Point \[text\] labelled "D(1, 3)" drawn in tree (location=(3.4, 0.4), marker\_radius=0.09); kid\_b1 — a Point \[text\] labelled "D(2, 3)" drawn in tree (location=(4.8, 0.4), marker\_radius=0.09); kid\_b2 — a Point \[text\] labelled "D(3, 2)" drawn in tree (location=(6.0, 0.4), marker\_radius=0.09); kid\_b3 — a Point \[text\] labelled "D(2, 2)" drawn in tree (location=(7.2, 0.4), marker\_radius=0.09); kid\_c1 — a Point \[text\] labelled "D(1, 3)" drawn in tree (location=(8.6, 0.4), marker\_radius=0.09); kid\_c2 — a Point \[text\] labelled "D(2, 2)" drawn in tree (location=(9.8, 0.4), marker\_radius=0.09); kid\_c3 — a Point \[text\] labelled "D(1, 2)" drawn in tree (location=(11.0, 0.4), marker\_radius=0.09) Actions: - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): caption is hidden from the screen — left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): head\_tree is hidden from the screen — left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): tree is hidden from the screen — left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): root is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_a is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_b is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_c is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): lvl\_a is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): lvl\_b is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): lvl\_c is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_a1 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_a2 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_a3 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_b1 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_b2 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_b3 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_c1 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_c2 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): edge\_c3 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): kid\_a1 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): kid\_a2 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): kid\_a3 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): kid\_b1 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): kid\_b2 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): kid\_b3 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): kid\_c1 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): kid\_c2 is hidden from the screen — tree left the board. - [04:10.201](https://academa.ai/lectures/edit-distance-dp-derivation?t=250.20102083333336): kid\_c3 is hidden from the screen — tree left the board. ### Scene 2: [What the Last Step Was](https://academa.ai/lectures/edit-distance-dp-derivation?t=251.24268750000002) Span: 04:11.243–07:41.032 (251.24268750000002s–461.0323125s). #### Objects - arr\_del: a Vector \[red\] labelled "+1" drawn in corner (start=(3.0, -0.5), end=(3.0, -1.5), trim\_tip=True) - arr\_ins: a Vector \[blue\] labelled "+1" drawn in corner (start=(1.0, -1.5), end=(3.0, -1.5), trim\_tip=True) - arr\_sub: a Vector \[yellow\] labelled "+c" drawn in corner (start=(1.0, -0.5), end=(3.0, -1.5), trim\_tip=True) - case\_del: a Math \[red\] that says "$upright("delete") : quad D(i-1, j) + 1$" - case\_ins: a Math \[blue\] that says "$upright("insert") : quad D(i, j-1) + 1$" - case\_sub: a Math \[yellow\] that says "$upright("substitute") : quad D(i-1, j-1) + c$" - corner: a Figure (x\_range=(-0.4, 4.4), y\_range=(-2.9, 0.6), aspect=(4.8, 3.5)) - cost\_def: a Math \[text\] that says "$c = 0 quad (A\_i = B\_j), quad c = 1 quad (A\_i eq.not B\_j)$" - h\_bot: a Line \[gray\] drawn in corner (start=(0.0, -2.0), end=(4.0, -2.0)) - h\_mid: a Line \[gray\] drawn in corner (start=(0.0, -1.0), end=(4.0, -1.0)) - h\_top: a Line \[gray\] drawn in corner (end=(4.0, 0.0)) - head\_last: a Heading that says "Ask What the Last Step Was" - head\_rec: a Heading that says "The Recurrence, and What It Cannot Do" - lbl\_diag: a Math \[text\] that says "$D(i-1, j-1)$" drawn in corner - lbl\_here: a Math \[text\] that says "$D(i, j)$" drawn in corner - lbl\_left: a Math \[text\] that says "$D(i, j-1)$" drawn in corner - lbl\_up: a Math \[text\] that says "$D(i-1, j)$" drawn in corner - need\_base: a Panel that says "Every case on the right names a smaller cell. Nothing here says what the smallest cells are." - point: a Point \[yellow\] drawn in corner (location=(1.0, -0.5)) - point\_2: a Point \[yellow\] drawn in corner (location=(3.0, -1.5)) - prompt: a Tex \[text\] that says "What was the last step?" - recurrence: a Math \[text\] that says "$D(i, j) = op("min") ( D(i-1, j) + 1, thin D(i, j-1) + 1, thin D(i-1, j-1) + c )$" - v\_left: a Line \[gray\] drawn in corner (end=(0.0, -2.0)) - v\_mid: a Line \[gray\] drawn in corner (start=(2.0, 0.0), end=(2.0, -2.0)) - v\_right: a Line \[gray\] drawn in corner (start=(4.0, 0.0), end=(4.0, -2.0)) #### Beats ##### [04:11.243](https://academa.ai/lectures/edit-distance-dp-derivation?t=251.24268750000002) Narration: The rule always comes out of the same question, whatever the problem happens to be. Look at the very end of both prefixes, and ask what the last step was. Board: Empty. Actions: - [04:11.243](https://academa.ai/lectures/edit-distance-dp-derivation?t=251.24268750000002): head\_last is shown on the screen, written out. - [04:11.243](https://academa.ai/lectures/edit-distance-dp-derivation?t=251.24268750000002): corner is shown on the screen, written out. - [04:17.536](https://academa.ai/lectures/edit-distance-dp-derivation?t=257.5356875): v\_left is shown on the screen, drawn. - [04:17.596](https://academa.ai/lectures/edit-distance-dp-derivation?t=257.5956875): v\_mid is shown on the screen, drawn. - [04:17.656](https://academa.ai/lectures/edit-distance-dp-derivation?t=257.6556875): v\_right is shown on the screen, drawn. - [04:17.716](https://academa.ai/lectures/edit-distance-dp-derivation?t=257.7156875): h\_top is shown on the screen, drawn. - [04:17.776](https://academa.ai/lectures/edit-distance-dp-derivation?t=257.7756875): h\_mid is shown on the screen, drawn. - [04:17.836](https://academa.ai/lectures/edit-distance-dp-derivation?t=257.8356875): h\_bot is shown on the screen, drawn. - [04:18.708](https://academa.ai/lectures/edit-distance-dp-derivation?t=258.7076875): prompt is shown on the screen, written out. ##### [04:21.317](https://academa.ai/lectures/edit-distance-dp-derivation?t=261.3166875) Narration: These four squares are a corner of the table we are about to build. The one at the bottom right is the cell we want, D of i and j. The other three are all strictly smaller subproblems: one row up, one column to the left, and one of each. Board: prompt — a Tex \[text\] that says "What was the last step?"; corner — a Figure (x\_range=(-0.4, 4.4), y\_range=(-2.9, 0.6), aspect=(4.8, 3.5)); head\_last — a Heading that says "Ask What the Last Step Was"; v\_left — a Line \[gray\] drawn in corner (end=(0.0, -2.0)); v\_mid — a Line \[gray\] drawn in corner (start=(2.0, 0.0), end=(2.0, -2.0)); v\_right — a Line \[gray\] drawn in corner (start=(4.0, 0.0), end=(4.0, -2.0)); h\_top — a Line \[gray\] drawn in corner (end=(4.0, 0.0)); h\_mid — a Line \[gray\] drawn in corner (start=(0.0, -1.0), end=(4.0, -1.0)); h\_bot — a Line \[gray\] drawn in corner (start=(0.0, -2.0), end=(4.0, -2.0)) Actions: - [04:26.541](https://academa.ai/lectures/edit-distance-dp-derivation?t=266.5406875): lbl\_here is shown on the screen, written out. - [04:34.459](https://academa.ai/lectures/edit-distance-dp-derivation?t=274.4586875): lbl\_up is shown on the screen, written out. - [04:35.423](https://academa.ai/lectures/edit-distance-dp-derivation?t=275.4226875): lbl\_left is shown on the screen, written out. - [04:37.095](https://academa.ai/lectures/edit-distance-dp-derivation?t=277.0946875): lbl\_diag is shown on the screen, written out. ##### [04:38.519](https://academa.ai/lectures/edit-distance-dp-derivation?t=278.5186875) Narration: Suppose the last edit deleted the source character A sub i. Then that character is gone, it was matched against nothing at all, and what is left over is the first i minus one characters of the source against the whole first j of the target. That is the cell directly above, plus one for the deletion itself. Board: prompt — a Tex \[text\] that says "What was the last step?"; corner — a Figure (x\_range=(-0.4, 4.4), y\_range=(-2.9, 0.6), aspect=(4.8, 3.5)); head\_last — a Heading that says "Ask What the Last Step Was"; v\_left — a Line \[gray\] drawn in corner (end=(0.0, -2.0)); v\_mid — a Line \[gray\] drawn in corner (start=(2.0, 0.0), end=(2.0, -2.0)); v\_right — a Line \[gray\] drawn in corner (start=(4.0, 0.0), end=(4.0, -2.0)); h\_top — a Line \[gray\] drawn in corner (end=(4.0, 0.0)); h\_mid — a Line \[gray\] drawn in corner (start=(0.0, -1.0), end=(4.0, -1.0)); h\_bot — a Line \[gray\] drawn in corner (start=(0.0, -2.0), end=(4.0, -2.0)); lbl\_here — a Math \[text\] that says "$D(i, j)$" drawn in corner; lbl\_up — a Math \[text\] that says "$D(i-1, j)$" drawn in corner; lbl\_left — a Math \[text\] that says "$D(i, j-1)$" drawn in corner; lbl\_diag — a Math \[text\] that says "$D(i-1, j-1)$" drawn in corner Actions: - [04:54.75](https://academa.ai/lectures/edit-distance-dp-derivation?t=294.74968750000005): arr\_del is shown on the screen, drawn. - [04:56.479](https://academa.ai/lectures/edit-distance-dp-derivation?t=296.47868750000004): case\_del is shown on the screen, written out. ##### [04:58.461](https://academa.ai/lectures/edit-distance-dp-derivation?t=298.4606875) Narration: Suppose instead that the last edit inserted the target character B sub j. Now the source is untouched, and it is the target that has one fewer character left to account for. That is the cell immediately to the left, plus one for the insertion. Board: prompt — a Tex \[text\] that says "What was the last step?"; case\_del — a Math \[red\] that says "$upright("delete") : quad D(i-1, j) + 1$"; corner — a Figure (x\_range=(-0.4, 4.4), y\_range=(-2.9, 0.6), aspect=(4.8, 3.5)); head\_last — a Heading that says "Ask What the Last Step Was"; v\_left — a Line \[gray\] drawn in corner (end=(0.0, -2.0)); v\_mid — a Line \[gray\] drawn in corner (start=(2.0, 0.0), end=(2.0, -2.0)); v\_right — a Line \[gray\] drawn in corner (start=(4.0, 0.0), end=(4.0, -2.0)); h\_top — a Line \[gray\] drawn in corner (end=(4.0, 0.0)); h\_mid — a Line \[gray\] drawn in corner (start=(0.0, -1.0), end=(4.0, -1.0)); h\_bot — a Line \[gray\] drawn in corner (start=(0.0, -2.0), end=(4.0, -2.0)); lbl\_here — a Math \[text\] that says "$D(i, j)$" drawn in corner; lbl\_up — a Math \[text\] that says "$D(i-1, j)$" drawn in corner; lbl\_left — a Math \[text\] that says "$D(i, j-1)$" drawn in corner; lbl\_diag — a Math \[text\] that says "$D(i-1, j-1)$" drawn in corner; arr\_del — a Vector \[red\] labelled "+1" drawn in corner (start=(3.0, -0.5), end=(3.0, -1.5), trim\_tip=True) Actions: - [05:8.422](https://academa.ai/lectures/edit-distance-dp-derivation?t=308.4216875): arr\_ins is shown on the screen, drawn. - [05:13.496](https://academa.ai/lectures/edit-distance-dp-derivation?t=313.49568750000003): case\_ins is shown on the screen, written out. ##### [05:15.071](https://academa.ai/lectures/edit-distance-dp-derivation?t=315.0711875) Narration: And the third possibility is that A sub i and B sub j were simply lined up against each other. Both prefixes lose a character, so we arrive from the diagonal. What that step costs depends entirely on the two characters. Board: prompt — a Tex \[text\] that says "What was the last step?"; case\_del — a Math \[red\] that says "$upright("delete") : quad D(i-1, j) + 1$"; case\_ins — a Math \[blue\] that says "$upright("insert") : quad D(i, j-1) + 1$"; corner — a Figure (x\_range=(-0.4, 4.4), y\_range=(-2.9, 0.6), aspect=(4.8, 3.5)); head\_last — a Heading that says "Ask What the Last Step Was"; v\_left — a Line \[gray\] drawn in corner (end=(0.0, -2.0)); v\_mid — a Line \[gray\] drawn in corner (start=(2.0, 0.0), end=(2.0, -2.0)); v\_right — a Line \[gray\] drawn in corner (start=(4.0, 0.0), end=(4.0, -2.0)); h\_top — a Line \[gray\] drawn in corner (end=(4.0, 0.0)); h\_mid — a Line \[gray\] drawn in corner (start=(0.0, -1.0), end=(4.0, -1.0)); h\_bot — a Line \[gray\] drawn in corner (start=(0.0, -2.0), end=(4.0, -2.0)); lbl\_here — a Math \[text\] that says "$D(i, j)$" drawn in corner; lbl\_up — a Math \[text\] that says "$D(i-1, j)$" drawn in corner; lbl\_left — a Math \[text\] that says "$D(i, j-1)$" drawn in corner; lbl\_diag — a Math \[text\] that says "$D(i-1, j-1)$" drawn in corner; arr\_del — a Vector \[red\] labelled "+1" drawn in corner (start=(3.0, -0.5), end=(3.0, -1.5), trim\_tip=True); arr\_ins — a Vector \[blue\] labelled "+1" drawn in corner (start=(1.0, -1.5), end=(3.0, -1.5), trim\_tip=True) Actions: - [05:24.917](https://academa.ai/lectures/edit-distance-dp-derivation?t=324.9166875): arr\_sub is shown on the screen, drawn. ##### [05:30.346](https://academa.ai/lectures/edit-distance-dp-derivation?t=330.34618750000004) Narration: That case is worth pausing on, because it is doing two jobs at once. When the two characters already agree, it is a match and it costs nothing at all. When they disagree, it is a substitution and it costs one. Same arrow, same neighbour, two different prices. Board: prompt — a Tex \[text\] that says "What was the last step?"; case\_del — a Math \[red\] that says "$upright("delete") : quad D(i-1, j) + 1$"; case\_ins — a Math \[blue\] that says "$upright("insert") : quad D(i, j-1) + 1$"; corner — a Figure (x\_range=(-0.4, 4.4), y\_range=(-2.9, 0.6), aspect=(4.8, 3.5)); head\_last — a Heading that says "Ask What the Last Step Was"; v\_left — a Line \[gray\] drawn in corner (end=(0.0, -2.0)); v\_mid — a Line \[gray\] drawn in corner (start=(2.0, 0.0), end=(2.0, -2.0)); v\_right — a Line \[gray\] drawn in corner (start=(4.0, 0.0), end=(4.0, -2.0)); h\_top — a Line \[gray\] drawn in corner (end=(4.0, 0.0)); h\_mid — a Line \[gray\] drawn in corner (start=(0.0, -1.0), end=(4.0, -1.0)); h\_bot — a Line \[gray\] drawn in corner (start=(0.0, -2.0), end=(4.0, -2.0)); lbl\_here — a Math \[text\] that says "$D(i, j)$" drawn in corner; lbl\_up — a Math \[text\] that says "$D(i-1, j)$" drawn in corner; lbl\_left — a Math \[text\] that says "$D(i, j-1)$" drawn in corner; lbl\_diag — a Math \[text\] that says "$D(i-1, j-1)$" drawn in corner; arr\_del — a Vector \[red\] labelled "+1" drawn in corner (start=(3.0, -0.5), end=(3.0, -1.5), trim\_tip=True); arr\_ins — a Vector \[blue\] labelled "+1" drawn in corner (start=(1.0, -1.5), end=(3.0, -1.5), trim\_tip=True); arr\_sub — a Vector \[yellow\] labelled "+c" drawn in corner (start=(1.0, -0.5), end=(3.0, -1.5), trim\_tip=True) Actions: - [05:37.463](https://academa.ai/lectures/edit-distance-dp-derivation?t=337.4626875): case\_sub is shown on the screen, written out. - [05:41.504](https://academa.ai/lectures/edit-distance-dp-derivation?t=341.5036875): arr\_sub is indicated — a transient flash. ##### [05:47.943](https://academa.ai/lectures/edit-distance-dp-derivation?t=347.94268750000003) Narration: Make that concrete. Take i equals two and j equals two, so the prefixes are s u and s a. The last characters are u and a. They are different, so that diagonal step costs one, sitting on top of whatever the distance between s and s turned out to be. Board: prompt — a Tex \[text\] that says "What was the last step?"; case\_del — a Math \[red\] that says "$upright("delete") : quad D(i-1, j) + 1$"; case\_ins — a Math \[blue\] that says "$upright("insert") : quad D(i, j-1) + 1$"; case\_sub — a Math \[yellow\] that says "$upright("substitute") : quad D(i-1, j-1) + c$"; corner — a Figure (x\_range=(-0.4, 4.4), y\_range=(-2.9, 0.6), aspect=(4.8, 3.5)); head\_last — a Heading that says "Ask What the Last Step Was"; v\_left — a Line \[gray\] drawn in corner (end=(0.0, -2.0)); v\_mid — a Line \[gray\] drawn in corner (start=(2.0, 0.0), end=(2.0, -2.0)); v\_right — a Line \[gray\] drawn in corner (start=(4.0, 0.0), end=(4.0, -2.0)); h\_top — a Line \[gray\] drawn in corner (end=(4.0, 0.0)); h\_mid — a Line \[gray\] drawn in corner (start=(0.0, -1.0), end=(4.0, -1.0)); h\_bot — a Line \[gray\] drawn in corner (start=(0.0, -2.0), end=(4.0, -2.0)); lbl\_here — a Math \[text\] that says "$D(i, j)$" drawn in corner; lbl\_up — a Math \[text\] that says "$D(i-1, j)$" drawn in corner; lbl\_left — a Math \[text\] that says "$D(i, j-1)$" drawn in corner; lbl\_diag — a Math \[text\] that says "$D(i-1, j-1)$" drawn in corner; arr\_del — a Vector \[red\] labelled "+1" drawn in corner (start=(3.0, -0.5), end=(3.0, -1.5), trim\_tip=True); arr\_ins — a Vector \[blue\] labelled "+1" drawn in corner (start=(1.0, -1.5), end=(3.0, -1.5), trim\_tip=True); arr\_sub — a Vector \[yellow\] labelled "+c" drawn in corner (start=(1.0, -0.5), end=(3.0, -1.5), trim\_tip=True) Actions: - [05:59.484](https://academa.ai/lectures/edit-distance-dp-derivation?t=359.48368750000003): point is shown on the screen, grown. - [06:1.084](https://academa.ai/lectures/edit-distance-dp-derivation?t=361.0836875): point is hidden from the screen. - [06:3.001](https://academa.ai/lectures/edit-distance-dp-derivation?t=363.0006875): point\_2 is shown on the screen, grown. - [06:4.601](https://academa.ai/lectures/edit-distance-dp-derivation?t=364.60068750000005): point\_2 is hidden from the screen. ##### [06:6.272](https://academa.ai/lectures/edit-distance-dp-derivation?t=366.27168750000004) Narration: Call that extra cost c. Zero when the two characters agree, one when they do not. That single letter is the only place the actual words enter the arithmetic. Everything else in the rule is pure bookkeeping. Board: Unchanged from the preceding beat in this scene. Actions: - [06:14.341](https://academa.ai/lectures/edit-distance-dp-derivation?t=374.34068750000006): arr\_sub is indicated — a transient flash. ##### [06:21.778](https://academa.ai/lectures/edit-distance-dp-derivation?t=381.77818750000006) Narration: Three cases, three neighbours, and no fourth possibility anywhere. Any edit sequence at all has to end in one of those three, so the cheapest sequence ends in whichever of the three is cheapest. Board: Unchanged from the preceding beat in this scene. Actions: - [06:23.636](https://academa.ai/lectures/edit-distance-dp-derivation?t=383.6356875): arr\_del is emphasized. - [06:23.636](https://academa.ai/lectures/edit-distance-dp-derivation?t=383.6356875): arr\_ins is emphasized. - [06:23.636](https://academa.ai/lectures/edit-distance-dp-derivation?t=383.6356875): arr\_sub is emphasized. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): case\_del is hidden from the screen — left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): case\_ins is hidden from the screen — left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): case\_sub is hidden from the screen — left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): corner is hidden from the screen — left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): v\_left is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): v\_mid is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): v\_right is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): h\_top is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): h\_mid is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): h\_bot is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): lbl\_here is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): lbl\_up is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): lbl\_left is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): lbl\_diag is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): arr\_del is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): arr\_ins is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): arr\_sub is hidden from the screen — corner left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): head\_last is hidden from the screen — left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): prompt is hidden from the screen — left the board. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): arr\_del is no longer emphasized. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): arr\_ins is no longer emphasized. - [06:34.56](https://academa.ai/lectures/edit-distance-dp-derivation?t=394.56018750000004): arr\_sub is no longer emphasized. ##### [06:35.76](https://academa.ai/lectures/edit-distance-dp-derivation?t=395.76018750000003) Narration: So there is the recurrence, and notice that we did not guess it and we did not remember it. It is nothing more than the minimum over the three ways the last step could have gone. Board: Empty. Actions: - [06:35.76](https://academa.ai/lectures/edit-distance-dp-derivation?t=395.76018750000003): head\_rec is shown on the screen, written out. - [06:36.759](https://academa.ai/lectures/edit-distance-dp-derivation?t=396.7586875): recurrence is shown on the screen, written out. ##### [06:46.693](https://academa.ai/lectures/edit-distance-dp-derivation?t=406.6931875) Narration: Read it as a picture rather than as algebra. One plus the cell above. One plus the cell to the left. Or c plus the cell on the diagonal. Take whichever of those three is smallest, and that is your answer. Board: recurrence — a Math \[text\] that says "$D(i, j) = op("min") ( D(i-1, j) + 1, thin D(i, j-1) + 1, thin D(i-1, j-1) + c )$"; head\_rec — a Heading that says "The Recurrence, and What It Cannot Do" Actions: - [06:51.093](https://academa.ai/lectures/edit-distance-dp-derivation?t=411.0926875): recurrence (the "D(i-1, j) + 1" part) is emphasized. - [06:53.392](https://academa.ai/lectures/edit-distance-dp-derivation?t=413.3916875): recurrence (the "D(i, j-1) + 1" part) is emphasized. - [06:53.392](https://academa.ai/lectures/edit-distance-dp-derivation?t=413.3916875): recurrence (the "D(i-1, j) + 1" part) is no longer emphasized. - [06:56.678](https://academa.ai/lectures/edit-distance-dp-derivation?t=416.6776875): recurrence (the "D(i, j-1) + 1" part) is no longer emphasized. - [06:56.678](https://academa.ai/lectures/edit-distance-dp-derivation?t=416.6776875): recurrence (the "D(i-1, j-1) + c" part) is emphasized. - [06:59.685](https://academa.ai/lectures/edit-distance-dp-derivation?t=419.6846875): recurrence (the "D(i-1, j-1) + c" part) is no longer emphasized. ##### [07:2.734](https://academa.ai/lectures/edit-distance-dp-derivation?t=422.7341875) Narration: And here is the cost, spelled out properly. c is zero if the character at position i and the character at position j are the same, and one if they are not. Board: Unchanged from the preceding beat in this scene. Actions: - [07:4.511](https://academa.ai/lectures/edit-distance-dp-derivation?t=424.5106875): cost\_def is shown on the screen, written out. - [07:10.804](https://academa.ai/lectures/edit-distance-dp-derivation?t=430.8036875): cost\_def is indicated — a transient flash. ##### [07:13.981](https://academa.ai/lectures/edit-distance-dp-derivation?t=433.98068750000004) Narration: There is a hole in this, though. Every one of those three cases points at a smaller cell, which is perfectly fine right up until the moment there is no smaller cell to point at. The recurrence cannot start itself. Board: recurrence — a Math \[text\] that says "$D(i, j) = op("min") ( D(i-1, j) + 1, thin D(i, j-1) + 1, thin D(i-1, j-1) + c )$"; cost\_def — a Math \[text\] that says "$c = 0 quad (A\_i = B\_j), quad c = 1 quad (A\_i eq.not B\_j)$"; head\_rec — a Heading that says "The Recurrence, and What It Cannot Do" Actions: - [07:14.794](https://academa.ai/lectures/edit-distance-dp-derivation?t=434.79368750000003): need\_base is shown on the screen, written out. - [07:25.091](https://academa.ai/lectures/edit-distance-dp-derivation?t=445.0906875): recurrence is indicated — a transient flash. ##### [07:26.968](https://academa.ai/lectures/edit-distance-dp-derivation?t=446.9681875) Narration: So we also need the cases that are true with no recursion at all. Those turn out to be the easy part, because a prefix of length zero is just the empty word. And that is where the table finally comes in. Board: recurrence — a Math \[text\] that says "$D(i, j) = op("min") ( D(i-1, j) + 1, thin D(i, j-1) + 1, thin D(i-1, j-1) + c )$"; cost\_def — a Math \[text\] that says "$c = 0 quad (A\_i = B\_j), quad c = 1 quad (A\_i eq.not B\_j)$"; need\_base — a Panel that says "Every case on the right names a smaller cell. Nothing here says what the smallest cells are."; head\_rec — a Heading that says "The Recurrence, and What It Cannot Do" Actions: - [07:39.991](https://academa.ai/lectures/edit-distance-dp-derivation?t=459.99064583333336): cost\_def is hidden from the screen — left the board. - [07:39.991](https://academa.ai/lectures/edit-distance-dp-derivation?t=459.99064583333336): head\_rec is hidden from the screen — left the board. - [07:39.991](https://academa.ai/lectures/edit-distance-dp-derivation?t=459.99064583333336): need\_base is hidden from the screen — left the board. - [07:39.991](https://academa.ai/lectures/edit-distance-dp-derivation?t=459.99064583333336): recurrence is hidden from the screen — left the board. ### Scene 3: [Filling It In, and Reading It Back](https://academa.ai/lectures/edit-distance-dp-derivation?t=461.0323125) Span: 07:41.032–15:42.502 (461.0323125s–942.5019374999999s). #### Objects - answer\_math: a Math \[text\] that says "$D(3, 4) = 2$" - arr\_diag: a Vector \[yellow\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True) - arr\_left: a Vector \[blue\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) - 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True) - arr\_up: a Vector \[red\] drawn in grid (start=((cx + 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True) - base\_math: a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$" - c00: a Math \[gray\] that says "$0$" drawn in grid - c01: a Math \[gray\] that says "$1$" drawn in grid - c02: a Math \[gray\] that says "$2$" drawn in grid - c03: a Math \[gray\] that says "$3$" drawn in grid - c04: a Math \[gray\] that says "$4$" drawn in grid - c10: a Math \[gray\] that says "$1$" drawn in grid - c11: a Math \[text\] that says "$0$" drawn in grid - c12: a Math \[text\] that says "$1$" drawn in grid - c13: a Math \[text\] that says "$2$" drawn in grid - c14: a Math \[text\] that says "$3$" drawn in grid - c20: a Math \[gray\] that says "$2$" drawn in grid - c21: a Math \[text\] that says "$1$" drawn in grid - c22: a Math \[text\] that says "$1$" drawn in grid - c23: a Math \[text\] that says "$2$" drawn in grid - c24: a Math \[text\] that says "$3$" drawn in grid - c30: a Math \[gray\] that says "$3$" drawn in grid - c31: a Math \[text\] that says "$2$" drawn in grid - c32: a Math \[text\] that says "$2$" drawn in grid - c33: a Math \[text\] that says "$1$" drawn in grid - c34: a Math \[text\] that says "$2$" drawn in grid - complexity: a Math \[text\] that says "$(m + 1)(n + 1) quad upright("cells, always")$" - counts: a Table \[text\] that says "Words Cells Naive calls sun to sand 20 193 kitten to sitting 56 29,737" (rows=(('Words', 'Cells', 'Naive calls'), ('sun to sand', '20', '193'…, header=True) - cx: a VariableNumber (initial\_value=1.0) - cy: a VariableNumber (initial\_value=1.0) - grid: a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)) - head\_back: a Heading that says "Walking the Arrows Backwards" - head\_cost: a Heading that says "What the Table Bought" - head\_method: a Heading that says "The Method, Without the Example" - head\_table: a Heading that says "The Table for sun and sand" - method: a Block \[text\] that says "Name the subproblem in one sentence. Ask what the last decision could have been. Let each answer point at a smaller subproblem. Write down the cases the rule cannot reach. Fill in an order that has every dependency ready." - path\_1: a Vector \[green\] drawn in grid (start=(4.5, -3.5), end=(3.5, -3.5), trim\_tip=True) - path\_2: a Vector \[green\] drawn in grid (start=(3.5, -3.5), end=(2.5, -2.5), trim\_tip=True) - path\_3: a Vector \[green\] drawn in grid (start=(2.5, -2.5), end=(1.5, -1.5), trim\_tip=True) - path\_4: a Vector \[green\] drawn in grid (start=(1.5, -1.5), end=(0.5, -0.5), trim\_tip=True) - point: a Point \[yellow\] drawn in grid (location=(4.5, -3.5)) - rec\_diag: a Math \[yellow\] that says "$upright("diagonal") : quad D(i-1, j-1) + c$" - rec\_left: a Math \[blue\] that says "$upright("left") : quad D(i, j-1) + 1$" - rec\_up: a Math \[red\] that says "$upright("above") : quad D(i-1, j) + 1$" - rules: a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0) - script: a Block \[text\] that says "Match the $s$ at the front. Free. Substitute the $u$ with an $a$. Cost one. Match the $n$ in the middle. Free. Insert a $d$ at the end. Cost one." - side\_n: a Math \[green\] that says "$upright("n")$" drawn in grid - side\_s: a Math \[green\] that says "$upright("s")$" drawn in grid - side\_u: a Math \[green\] that says "$upright("u")$" drawn in grid - top\_a: a Math \[green\] that says "$upright("a")$" drawn in grid - top\_d: a Math \[green\] that says "$upright("d")$" drawn in grid - top\_n: a Math \[green\] that says "$upright("n")$" drawn in grid - top\_s: a Math \[green\] that says "$upright("s")$" drawn in grid - work: a Math \[text\] that says "$D(1, 1) = op("min")(2, thin 2, thin 0) = 0$" #### Beats ##### [07:41.032](https://academa.ai/lectures/edit-distance-dp-derivation?t=461.0323125) Narration: Here is the table. Four rows, because sun has three characters and we need a row for zero characters as well. Five columns, for the same reason, with sand. Board: Empty. Actions: - [07:41.032](https://academa.ai/lectures/edit-distance-dp-derivation?t=461.0323125): head\_table is shown on the screen, written out. - [07:41.032](https://academa.ai/lectures/edit-distance-dp-derivation?t=461.0323125): grid is shown on the screen, written out. - [07:42.82](https://academa.ai/lectures/edit-distance-dp-derivation?t=462.8203125): rules is shown on the screen, written out. - [07:43.9](https://academa.ai/lectures/edit-distance-dp-derivation?t=463.9003125): side\_s is shown on the screen, written out. - [07:44](https://academa.ai/lectures/edit-distance-dp-derivation?t=464.0003125): side\_u is shown on the screen, written out. - [07:44.1](https://academa.ai/lectures/edit-distance-dp-derivation?t=464.1003125): side\_n is shown on the screen, written out. - [07:48.52](https://academa.ai/lectures/edit-distance-dp-derivation?t=468.5203125): top\_s is shown on the screen, written out. - [07:48.62](https://academa.ai/lectures/edit-distance-dp-derivation?t=468.6203125): top\_a is shown on the screen, written out. - [07:48.72](https://academa.ai/lectures/edit-distance-dp-derivation?t=468.7203125): top\_n is shown on the screen, written out. - [07:48.82](https://academa.ai/lectures/edit-distance-dp-derivation?t=468.8203125): top\_d is shown on the screen, written out. ##### [07:51.93](https://academa.ai/lectures/edit-distance-dp-derivation?t=471.9303125) Narration: Every single square in it is one subproblem. The square in row i and column j is going to hold D of i and j, and the one we actually want is down there in the bottom right corner. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid Actions: - [08:2.843](https://academa.ai/lectures/edit-distance-dp-derivation?t=482.84331249999997): point is shown on the screen, grown. ##### [08:4.256](https://academa.ai/lectures/edit-distance-dp-derivation?t=484.2563125) Narration: Start with row zero. That row is the source prefix of length zero, which is the empty word. Turning the empty word into the first j characters of sand costs exactly j insertions, one per character, so row zero simply counts up. Zero, one, two, three, four. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; point — a Point \[yellow\] drawn in grid (location=(4.5, -3.5)) Actions: - [08:4.843](https://academa.ai/lectures/edit-distance-dp-derivation?t=484.84331249999997): point is hidden from the screen. - [08:5.371](https://academa.ai/lectures/edit-distance-dp-derivation?t=485.3713125): c00 is shown on the screen, written out. - [08:16.69](https://academa.ai/lectures/edit-distance-dp-derivation?t=496.6903125): c01 is shown on the screen, written out. - [08:22.031](https://academa.ai/lectures/edit-distance-dp-derivation?t=502.0313125): c02 is shown on the screen, written out. - [08:22.588](https://academa.ai/lectures/edit-distance-dp-derivation?t=502.5883125): c03 is shown on the screen, written out. - [08:23.169](https://academa.ai/lectures/edit-distance-dp-derivation?t=503.1693125): c04 is shown on the screen, written out. ##### [08:24.593](https://academa.ai/lectures/edit-distance-dp-derivation?t=504.59331249999997) Narration: Column zero is the mirror image of that. Turning the first i characters of sun into the empty word costs i deletions, so it counts down the side. One, two, three. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid Actions: - [08:34.914](https://academa.ai/lectures/edit-distance-dp-derivation?t=514.9143124999999): c10 is shown on the screen, written out. - [08:35.645](https://academa.ai/lectures/edit-distance-dp-derivation?t=515.6453125): c20 is shown on the screen, written out. - [08:36.365](https://academa.ai/lectures/edit-distance-dp-derivation?t=516.3653125): c30 is shown on the screen, written out. ##### [08:37.825](https://academa.ai/lectures/edit-distance-dp-derivation?t=517.8248125) Narration: Those eight squares are true by definition rather than by any rule. And look at the corner one: no characters against no characters, nothing to do, zero. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid Actions: - [08:39.961](https://academa.ai/lectures/edit-distance-dp-derivation?t=519.9613125): grid moves to a new place on the board. - [08:39.961](https://academa.ai/lectures/edit-distance-dp-derivation?t=519.9613125): base\_math is shown on the screen, written out. - [08:47.704](https://academa.ai/lectures/edit-distance-dp-derivation?t=527.7043125): c00 is indicated — a transient flash. ##### [08:49.14](https://academa.ai/lectures/edit-distance-dp-derivation?t=529.1403124999999) Narration: Everything else comes from the rule we derived, and the three ways in keep the three colours from before: red from above, blue from the left, yellow from the diagonal. Twelve squares left, and each one is the smallest of three numbers already sitting on the page. Board: base\_math — a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$"; grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid Actions: - [08:55.177](https://academa.ai/lectures/edit-distance-dp-derivation?t=535.1773125): rec\_up is shown on the screen, written out. - [08:56.222](https://academa.ai/lectures/edit-distance-dp-derivation?t=536.2223125): rec\_left is shown on the screen, written out. - [08:57.453](https://academa.ai/lectures/edit-distance-dp-derivation?t=537.4533125): rec\_diag is shown on the screen, written out. ##### [09:4.95](https://academa.ai/lectures/edit-distance-dp-derivation?t=544.9498125) Narration: Take the first empty one, row one, column one. Row one means the source prefix is s. Column one means the target prefix is s. Three arrows point into that square, one from each neighbour, and the square holds the smallest of what those three arrows offer. Board: base\_math — a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$"; rec\_up — a Math \[red\] that says "$upright("above") : quad D(i-1, j) + 1$"; rec\_left — a Math \[blue\] that says "$upright("left") : quad D(i, j-1) + 1$"; rec\_diag — a Math \[yellow\] that says "$upright("diagonal") : quad D(i-1, j-1) + c$"; grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid Actions: - [09:14.238](https://academa.ai/lectures/edit-distance-dp-derivation?t=554.2383125): arr\_up is shown on the screen, drawn. - [09:14.238](https://academa.ai/lectures/edit-distance-dp-derivation?t=554.2383125): arr\_left is shown on the screen, drawn. - [09:14.238](https://academa.ai/lectures/edit-distance-dp-derivation?t=554.2383125): arr\_diag is shown on the screen, drawn. ##### [09:21.247](https://academa.ai/lectures/edit-distance-dp-derivation?t=561.2468125) Narration: From above, the neighbour holds one, and a deletion costs one more, so two. From the left, one again, plus one for an insertion, so two again. From the diagonal, zero, and both characters here are s, so c is zero and the diagonal asks for nothing extra. Board: base\_math — a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$"; rec\_up — a Math \[red\] that says "$upright("above") : quad D(i-1, j) + 1$"; rec\_left — a Math \[blue\] that says "$upright("left") : quad D(i, j-1) + 1$"; rec\_diag — a Math \[yellow\] that says "$upright("diagonal") : quad D(i-1, j-1) + c$"; grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; arr\_up — a Vector \[red\] drawn in grid (start=((cx + 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_left — a Vector \[blue\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) - 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_diag — a Vector \[yellow\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True) Actions: - [09:21.769](https://academa.ai/lectures/edit-distance-dp-derivation?t=561.7693125): c01 is emphasized. - [09:27.028](https://academa.ai/lectures/edit-distance-dp-derivation?t=567.0283125): c01 is no longer emphasized. - [09:27.028](https://academa.ai/lectures/edit-distance-dp-derivation?t=567.0283125): c10 is emphasized. - [09:31.742](https://academa.ai/lectures/edit-distance-dp-derivation?t=571.7423125): c10 is no longer emphasized. - [09:31.742](https://academa.ai/lectures/edit-distance-dp-derivation?t=571.7423125): c00 is emphasized. - [09:39.277](https://academa.ai/lectures/edit-distance-dp-derivation?t=579.2773125): c00 is no longer emphasized. ##### [09:39.877](https://academa.ai/lectures/edit-distance-dp-derivation?t=579.8773125) Narration: Zero wins, so the square is zero, and that is exactly right. Turning s into s costs nothing at all. Board: Unchanged from the preceding beat in this scene. Actions: - [09:40.817](https://academa.ai/lectures/edit-distance-dp-derivation?t=580.8173125): work is shown on the screen, written out. - [09:41.746](https://academa.ai/lectures/edit-distance-dp-derivation?t=581.7463125): c11 is shown on the screen, written out. - [09:46.135](https://academa.ai/lectures/edit-distance-dp-derivation?t=586.1353125): c11 is indicated — a transient flash. ##### [09:47.943](https://academa.ai/lectures/edit-distance-dp-derivation?t=587.9428125) Narration: Now slide the arrows one column to the right. Row one is still just s. Column two is s a. From above, three. From the left, one. From the diagonal, one, and this time the characters are s and a, which differ, so add one and you get two. The smallest is one. Board: base\_math — a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$"; rec\_up — a Math \[red\] that says "$upright("above") : quad D(i-1, j) + 1$"; rec\_left — a Math \[blue\] that says "$upright("left") : quad D(i, j-1) + 1$"; rec\_diag — a Math \[yellow\] that says "$upright("diagonal") : quad D(i-1, j-1) + c$"; work — a Math \[text\] that says "$D(1, 1) = op("min")(2, thin 2, thin 0) = 0$"; grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; arr\_up — a Vector \[red\] drawn in grid (start=((cx + 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_left — a Vector \[blue\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) - 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_diag — a Vector \[yellow\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); c11 — a Math \[text\] that says "$0$" drawn in grid Actions: - [09:48.616](https://academa.ai/lectures/edit-distance-dp-derivation?t=588.6163125): arr\_up is redrawn as the numbers it depends on change. - [09:48.616](https://academa.ai/lectures/edit-distance-dp-derivation?t=588.6163125): arr\_left is redrawn as the numbers it depends on change. - [09:48.616](https://academa.ai/lectures/edit-distance-dp-derivation?t=588.6163125): arr\_diag is redrawn as the numbers it depends on change. - [09:48.616](https://academa.ai/lectures/edit-distance-dp-derivation?t=588.6163125): cx ticks to 2.0. - [09:55.558](https://academa.ai/lectures/edit-distance-dp-derivation?t=595.5583125): work becomes "$D(1, 2) = op("min")(3, thin 1, thin 2) = 1$". - [10:5.821](https://academa.ai/lectures/edit-distance-dp-derivation?t=605.8213125): c12 is shown on the screen, written out. ##### [10:7.444](https://academa.ai/lectures/edit-distance-dp-derivation?t=607.4438124999999) Narration: One insertion. Build s a out of a single s by adding an a on the end. The table just derived that on its own, and it will keep doing it. Board: base\_math — a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$"; rec\_up — a Math \[red\] that says "$upright("above") : quad D(i-1, j) + 1$"; rec\_left — a Math \[blue\] that says "$upright("left") : quad D(i, j-1) + 1$"; rec\_diag — a Math \[yellow\] that says "$upright("diagonal") : quad D(i-1, j-1) + c$"; work — a Math \[text\] that says "$D(1, 1) = op("min")(2, thin 2, thin 0) = 0$"; grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; arr\_up — a Vector \[red\] drawn in grid (start=((cx + 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_left — a Vector \[blue\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) - 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_diag — a Vector \[yellow\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid Actions: - [10:7.791](https://academa.ai/lectures/edit-distance-dp-derivation?t=607.7913125): c12 is indicated — a transient flash. ##### [10:16.681](https://academa.ai/lectures/edit-distance-dp-derivation?t=616.6813125) Narration: The rest of that row goes the same way. Column three, two. Column four, three. Row one now reads one, zero, one, two, three, and each of those is the cost of building a longer and longer prefix of sand out of one s. Board: Unchanged from the preceding beat in this scene. Actions: - [10:19.955](https://academa.ai/lectures/edit-distance-dp-derivation?t=619.9553125): arr\_up is redrawn as the numbers it depends on change. - [10:19.955](https://academa.ai/lectures/edit-distance-dp-derivation?t=619.9553125): arr\_left is redrawn as the numbers it depends on change. - [10:19.955](https://academa.ai/lectures/edit-distance-dp-derivation?t=619.9553125): arr\_diag is redrawn as the numbers it depends on change. - [10:19.955](https://academa.ai/lectures/edit-distance-dp-derivation?t=619.9553125): work becomes "$D(1, 3) = op("min")(4, thin 2, thin 3) = 2$". - [10:19.955](https://academa.ai/lectures/edit-distance-dp-derivation?t=619.9553125): cx ticks to 3.0. - [10:20.385](https://academa.ai/lectures/edit-distance-dp-derivation?t=620.3853125): c13 is shown on the screen, written out. - [10:21.987](https://academa.ai/lectures/edit-distance-dp-derivation?t=621.9873125): arr\_up is redrawn as the numbers it depends on change. - [10:21.987](https://academa.ai/lectures/edit-distance-dp-derivation?t=621.9873125): arr\_left is redrawn as the numbers it depends on change. - [10:21.987](https://academa.ai/lectures/edit-distance-dp-derivation?t=621.9873125): arr\_diag is redrawn as the numbers it depends on change. - [10:21.987](https://academa.ai/lectures/edit-distance-dp-derivation?t=621.9873125): work becomes "$D(1, 4) = op("min")(5, thin 3, thin 4) = 3$". - [10:21.987](https://academa.ai/lectures/edit-distance-dp-derivation?t=621.9873125): cx ticks to 4.0. - [10:22.416](https://academa.ai/lectures/edit-distance-dp-derivation?t=622.4163125): c14 is shown on the screen, written out. ##### [10:33.733](https://academa.ai/lectures/edit-distance-dp-derivation?t=633.7328125) Narration: Row two now, so the source prefix is s u. Back to column one, where the target is s. From above, zero plus one is one. From the left, two plus one is three. From the diagonal, one plus one is two, because u and s are different. One wins. Board: base\_math — a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$"; rec\_up — a Math \[red\] that says "$upright("above") : quad D(i-1, j) + 1$"; rec\_left — a Math \[blue\] that says "$upright("left") : quad D(i, j-1) + 1$"; rec\_diag — a Math \[yellow\] that says "$upright("diagonal") : quad D(i-1, j-1) + c$"; work — a Math \[text\] that says "$D(1, 1) = op("min")(2, thin 2, thin 0) = 0$"; grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; arr\_up — a Vector \[red\] drawn in grid (start=((cx + 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_left — a Vector \[blue\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) - 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_diag — a Vector \[yellow\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid Actions: - [10:34.081](https://academa.ai/lectures/edit-distance-dp-derivation?t=634.0813125): arr\_up is redrawn as the numbers it depends on change. - [10:34.081](https://academa.ai/lectures/edit-distance-dp-derivation?t=634.0813125): arr\_left is redrawn as the numbers it depends on change. - [10:34.081](https://academa.ai/lectures/edit-distance-dp-derivation?t=634.0813125): arr\_diag is redrawn as the numbers it depends on change. - [10:34.081](https://academa.ai/lectures/edit-distance-dp-derivation?t=634.0813125): cy ticks to 2.0. - [10:34.081](https://academa.ai/lectures/edit-distance-dp-derivation?t=634.0813125): cx ticks to 1.0. - [10:41.302](https://academa.ai/lectures/edit-distance-dp-derivation?t=641.3023125): work becomes "$D(2, 1) = op("min")(1, thin 3, thin 2) = 1$". - [10:51.774](https://academa.ai/lectures/edit-distance-dp-derivation?t=651.7743125000001): c21 is shown on the screen, written out. ##### [10:53.246](https://academa.ai/lectures/edit-distance-dp-derivation?t=653.2458125) Narration: And notice which arrow it came from. The one from above, the red one, which is a deletion. Turning s u into s means throwing the u away, and the table found that by itself. Board: base\_math — a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$"; rec\_up — a Math \[red\] that says "$upright("above") : quad D(i-1, j) + 1$"; rec\_left — a Math \[blue\] that says "$upright("left") : quad D(i, j-1) + 1$"; rec\_diag — a Math \[yellow\] that says "$upright("diagonal") : quad D(i-1, j-1) + c$"; work — a Math \[text\] that says "$D(1, 1) = op("min")(2, thin 2, thin 0) = 0$"; grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; arr\_up — a Vector \[red\] drawn in grid (start=((cx + 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_left — a Vector \[blue\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) - 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_diag — a Vector \[yellow\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid Actions: - [10:57.738](https://academa.ai/lectures/edit-distance-dp-derivation?t=657.7383125): arr\_up is indicated — a transient flash. - [11:2.324](https://academa.ai/lectures/edit-distance-dp-derivation?t=662.3243125): c21 is indicated — a transient flash. ##### [11:5.966](https://academa.ai/lectures/edit-distance-dp-derivation?t=665.9663125) Narration: This next one is the interesting square. Row two, column two: s u against s a. From above, two. From the left, two. From the diagonal, zero plus one, because u and a differ. One, from the diagonal, and that diagonal step is exactly the substitution we spotted by eye at the very start. Board: Unchanged from the preceding beat in this scene. Actions: - [11:6.988](https://academa.ai/lectures/edit-distance-dp-derivation?t=666.9883125): c22 is shown on the screen, written out. - [11:7.986](https://academa.ai/lectures/edit-distance-dp-derivation?t=667.9863125): arr\_up is redrawn as the numbers it depends on change. - [11:7.986](https://academa.ai/lectures/edit-distance-dp-derivation?t=667.9863125): arr\_left is redrawn as the numbers it depends on change. - [11:7.986](https://academa.ai/lectures/edit-distance-dp-derivation?t=667.9863125): arr\_diag is redrawn as the numbers it depends on change. - [11:7.986](https://academa.ai/lectures/edit-distance-dp-derivation?t=667.9863125): cx ticks to 2.0. - [11:13.385](https://academa.ai/lectures/edit-distance-dp-derivation?t=673.3853125): work becomes "$D(2, 2) = op("min")(2, thin 2, thin 1) = 1$". - [11:24.647](https://academa.ai/lectures/edit-distance-dp-derivation?t=684.6473125): arr\_diag is indicated — a transient flash. ##### [11:28.439](https://academa.ai/lectures/edit-distance-dp-derivation?t=688.4393125) Narration: Finish the row. Column three gives two. Column four gives three. Nothing matches anywhere along there, so every step is costing something. Board: base\_math — a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$"; rec\_up — a Math \[red\] that says "$upright("above") : quad D(i-1, j) + 1$"; rec\_left — a Math \[blue\] that says "$upright("left") : quad D(i, j-1) + 1$"; rec\_diag — a Math \[yellow\] that says "$upright("diagonal") : quad D(i-1, j-1) + c$"; work — a Math \[text\] that says "$D(1, 1) = op("min")(2, thin 2, thin 0) = 0$"; grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; arr\_up — a Vector \[red\] drawn in grid (start=((cx + 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_left — a Vector \[blue\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) - 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_diag — a Vector \[yellow\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid Actions: - [11:30.134](https://academa.ai/lectures/edit-distance-dp-derivation?t=690.1343125000001): arr\_up is redrawn as the numbers it depends on change. - [11:30.134](https://academa.ai/lectures/edit-distance-dp-derivation?t=690.1343125000001): arr\_left is redrawn as the numbers it depends on change. - [11:30.134](https://academa.ai/lectures/edit-distance-dp-derivation?t=690.1343125000001): arr\_diag is redrawn as the numbers it depends on change. - [11:30.134](https://academa.ai/lectures/edit-distance-dp-derivation?t=690.1343125000001): work becomes "$D(2, 3) = op("min")(3, thin 2, thin 2) = 2$". - [11:30.134](https://academa.ai/lectures/edit-distance-dp-derivation?t=690.1343125000001): cx ticks to 3.0. - [11:30.738](https://academa.ai/lectures/edit-distance-dp-derivation?t=690.7383125): c23 is shown on the screen, written out. - [11:31.946](https://academa.ai/lectures/edit-distance-dp-derivation?t=691.9463125): arr\_up is redrawn as the numbers it depends on change. - [11:31.946](https://academa.ai/lectures/edit-distance-dp-derivation?t=691.9463125): arr\_left is redrawn as the numbers it depends on change. - [11:31.946](https://academa.ai/lectures/edit-distance-dp-derivation?t=691.9463125): arr\_diag is redrawn as the numbers it depends on change. - [11:31.946](https://academa.ai/lectures/edit-distance-dp-derivation?t=691.9463125): work becomes "$D(2, 4) = op("min")(4, thin 3, thin 3) = 3$". - [11:31.946](https://academa.ai/lectures/edit-distance-dp-derivation?t=691.9463125): cx ticks to 4.0. - [11:32.503](https://academa.ai/lectures/edit-distance-dp-derivation?t=692.5033125): c24 is shown on the screen, written out. ##### [11:37.84](https://academa.ai/lectures/edit-distance-dp-derivation?t=697.8403125) Narration: Last row, so the source is the whole word, s u n. Column one gives two. Column two gives two as well. Board: base\_math — a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$"; rec\_up — a Math \[red\] that says "$upright("above") : quad D(i-1, j) + 1$"; rec\_left — a Math \[blue\] that says "$upright("left") : quad D(i, j-1) + 1$"; rec\_diag — a Math \[yellow\] that says "$upright("diagonal") : quad D(i-1, j-1) + c$"; work — a Math \[text\] that says "$D(1, 1) = op("min")(2, thin 2, thin 0) = 0$"; grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; arr\_up — a Vector \[red\] drawn in grid (start=((cx + 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_left — a Vector \[blue\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) - 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_diag — a Vector \[yellow\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid Actions: - [11:38.397](https://academa.ai/lectures/edit-distance-dp-derivation?t=698.3973125): arr\_up is redrawn as the numbers it depends on change. - [11:38.397](https://academa.ai/lectures/edit-distance-dp-derivation?t=698.3973125): arr\_left is redrawn as the numbers it depends on change. - [11:38.397](https://academa.ai/lectures/edit-distance-dp-derivation?t=698.3973125): arr\_diag is redrawn as the numbers it depends on change. - [11:38.397](https://academa.ai/lectures/edit-distance-dp-derivation?t=698.3973125): cy ticks to 3.0. - [11:38.397](https://academa.ai/lectures/edit-distance-dp-derivation?t=698.3973125): cx ticks to 1.0. - [11:41.961](https://academa.ai/lectures/edit-distance-dp-derivation?t=701.9613125000001): work becomes "$D(3, 1) = op("min")(2, thin 4, thin 3) = 2$". - [11:43.018](https://academa.ai/lectures/edit-distance-dp-derivation?t=703.0183125000001): c31 is shown on the screen, written out. - [11:44.237](https://academa.ai/lectures/edit-distance-dp-derivation?t=704.2373125): arr\_up is redrawn as the numbers it depends on change. - [11:44.237](https://academa.ai/lectures/edit-distance-dp-derivation?t=704.2373125): arr\_left is redrawn as the numbers it depends on change. - [11:44.237](https://academa.ai/lectures/edit-distance-dp-derivation?t=704.2373125): arr\_diag is redrawn as the numbers it depends on change. - [11:44.237](https://academa.ai/lectures/edit-distance-dp-derivation?t=704.2373125): work becomes "$D(3, 2) = op("min")(2, thin 3, thin 2) = 2$". - [11:44.237](https://academa.ai/lectures/edit-distance-dp-derivation?t=704.2373125): cx ticks to 2.0. - [11:45.073](https://academa.ai/lectures/edit-distance-dp-derivation?t=705.0733125): c32 is shown on the screen, written out. ##### [11:46.271](https://academa.ai/lectures/edit-distance-dp-derivation?t=706.2708125) Narration: Column three is worth slowing down for. Source s u n, target s a n. The last characters are both n, so c is zero, and the diagonal offers one plus nothing. Above offers three, the left offers three, the diagonal offers one. The number drops. Board: base\_math — a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$"; rec\_up — a Math \[red\] that says "$upright("above") : quad D(i-1, j) + 1$"; rec\_left — a Math \[blue\] that says "$upright("left") : quad D(i, j-1) + 1$"; rec\_diag — a Math \[yellow\] that says "$upright("diagonal") : quad D(i-1, j-1) + c$"; work — a Math \[text\] that says "$D(1, 1) = op("min")(2, thin 2, thin 0) = 0$"; grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; arr\_up — a Vector \[red\] drawn in grid (start=((cx + 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_left — a Vector \[blue\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) - 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_diag — a Vector \[yellow\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid Actions: - [11:47.531](https://academa.ai/lectures/edit-distance-dp-derivation?t=707.5313125): arr\_up is redrawn as the numbers it depends on change. - [11:47.531](https://academa.ai/lectures/edit-distance-dp-derivation?t=707.5313125): arr\_left is redrawn as the numbers it depends on change. - [11:47.531](https://academa.ai/lectures/edit-distance-dp-derivation?t=707.5313125): arr\_diag is redrawn as the numbers it depends on change. - [11:47.531](https://academa.ai/lectures/edit-distance-dp-derivation?t=707.5313125): cx ticks to 3.0. - [11:58.037](https://academa.ai/lectures/edit-distance-dp-derivation?t=718.0373125000001): work becomes "$D(3, 3) = op("min")(3, thin 3, thin 1) = 1$". - [12:2.786](https://academa.ai/lectures/edit-distance-dp-derivation?t=722.7863125): c33 is shown on the screen, written out. ##### [12:4.182](https://academa.ai/lectures/edit-distance-dp-derivation?t=724.1818125) Narration: That is a free match paying for itself. And now the very last square. Source s u n, target s a n d. The last characters are n and d, which differ. Above gives four. The diagonal gives three. And from the left, one plus one is two. Board: base\_math — a Math \[text\] that says "$D(i, 0) = i, quad D(0, j) = j$"; rec\_up — a Math \[red\] that says "$upright("above") : quad D(i-1, j) + 1$"; rec\_left — a Math \[blue\] that says "$upright("left") : quad D(i, j-1) + 1$"; rec\_diag — a Math \[yellow\] that says "$upright("diagonal") : quad D(i-1, j-1) + c$"; work — a Math \[text\] that says "$D(1, 1) = op("min")(2, thin 2, thin 0) = 0$"; grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); head\_table — a Heading that says "The Table for sun and sand"; rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; arr\_up — a Vector \[red\] drawn in grid (start=((cx + 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_left — a Vector \[blue\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) - 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_diag — a Vector \[yellow\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid; c33 — a Math \[text\] that says "$1$" drawn in grid Actions: - [12:4.814](https://academa.ai/lectures/edit-distance-dp-derivation?t=724.8143125): c33 is indicated — a transient flash. - [12:7.844](https://academa.ai/lectures/edit-distance-dp-derivation?t=727.8443125): arr\_up is redrawn as the numbers it depends on change. - [12:7.844](https://academa.ai/lectures/edit-distance-dp-derivation?t=727.8443125): arr\_left is redrawn as the numbers it depends on change. - [12:7.844](https://academa.ai/lectures/edit-distance-dp-derivation?t=727.8443125): arr\_diag is redrawn as the numbers it depends on change. - [12:7.844](https://academa.ai/lectures/edit-distance-dp-derivation?t=727.8443125): cx ticks to 4.0. - [12:16.238](https://academa.ai/lectures/edit-distance-dp-derivation?t=736.2383125): work becomes "$D(3, 4) = op("min")(4, thin 2, thin 3) = 2$". ##### [12:22.678](https://academa.ai/lectures/edit-distance-dp-derivation?t=742.6783125) Narration: Two. That is the edit distance between sun and sand, and every one of those twenty numbers was worked out exactly once, from numbers already sitting above it and to its left. Board: Unchanged from the preceding beat in this scene. Actions: - [12:22.98](https://academa.ai/lectures/edit-distance-dp-derivation?t=742.9803125000001): c34 is shown on the screen, written out. - [12:25](https://academa.ai/lectures/edit-distance-dp-derivation?t=745.0003125000001): A box is drawn around c34. - [12:33.522](https://academa.ai/lectures/edit-distance-dp-derivation?t=753.5223125): base\_math is hidden from the screen — left the board. - [12:33.522](https://academa.ai/lectures/edit-distance-dp-derivation?t=753.5223125): head\_table is hidden from the screen — left the board. - [12:33.522](https://academa.ai/lectures/edit-distance-dp-derivation?t=753.5223125): rec\_diag is hidden from the screen — left the board. - [12:33.522](https://academa.ai/lectures/edit-distance-dp-derivation?t=753.5223125): rec\_left is hidden from the screen — left the board. - [12:33.522](https://academa.ai/lectures/edit-distance-dp-derivation?t=753.5223125): rec\_up is hidden from the screen — left the board. - [12:33.522](https://academa.ai/lectures/edit-distance-dp-derivation?t=753.5223125): work is hidden from the screen — left the board. ##### [12:34.722](https://academa.ai/lectures/edit-distance-dp-derivation?t=754.7223125) Narration: Now the number on its own is not really the interesting part. The table also knows which moves it used to get there, and we can read them back out by walking the winning arrows backwards from the corner. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; arr\_up — a Vector \[red\] drawn in grid (start=((cx + 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_left — a Vector \[blue\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) - 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); arr\_diag — a Vector \[yellow\] drawn in grid (start=((cx - 0.5), ((cy \* -1.0) + 0.5)), end=((cx + 0.5), ((cy \* -1.0) - 0.5)), trim\_tip=True); c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid; c33 — a Math \[text\] that says "$1$" drawn in grid; c34 — a Math \[text\] that says "$2$" drawn in grid Actions: - [12:34.722](https://academa.ai/lectures/edit-distance-dp-derivation?t=754.7223125): head\_back is shown on the screen, written out. - [12:35.384](https://academa.ai/lectures/edit-distance-dp-derivation?t=755.3843125000001): answer\_math is shown on the screen, written out. - [12:42.211](https://academa.ai/lectures/edit-distance-dp-derivation?t=762.2113125000001): arr\_up is hidden from the screen. - [12:42.211](https://academa.ai/lectures/edit-distance-dp-derivation?t=762.2113125000001): arr\_left is hidden from the screen. - [12:42.211](https://academa.ai/lectures/edit-distance-dp-derivation?t=762.2113125000001): arr\_diag is hidden from the screen. ##### [12:45.4](https://academa.ai/lectures/edit-distance-dp-derivation?t=765.3998125) Narration: Start at the bottom right. The two there came from the left neighbour, which held one. A step from the left is an insertion, so the last edit was inserting the d. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid; c33 — a Math \[text\] that says "$1$" drawn in grid; c34 — a Math \[text\] that says "$2$" drawn in grid; answer\_math — a Math \[text\] that says "$D(3, 4) = 2$"; head\_back — a Heading that says "Walking the Arrows Backwards" Actions: - [12:48.674](https://academa.ai/lectures/edit-distance-dp-derivation?t=768.6743125): path\_1 is shown on the screen, drawn. - [12:49.893](https://academa.ai/lectures/edit-distance-dp-derivation?t=769.8933125): c33 is indicated — a transient flash. ##### [12:55.167](https://academa.ai/lectures/edit-distance-dp-derivation?t=775.1668125) Narration: From that square, the one came from the diagonal, and the characters there were n and n, equal, so the step cost nothing. A free diagonal step is a match. Keep the n exactly as it is. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid; c33 — a Math \[text\] that says "$1$" drawn in grid; c34 — a Math \[text\] that says "$2$" drawn in grid; answer\_math — a Math \[text\] that says "$D(3, 4) = 2$"; head\_back — a Heading that says "Walking the Arrows Backwards"; path\_1 — a Vector \[green\] drawn in grid (start=(4.5, -3.5), end=(3.5, -3.5), trim\_tip=True) Actions: - [12:57.424](https://academa.ai/lectures/edit-distance-dp-derivation?t=777.4243125): path\_2 is shown on the screen, drawn. - [13:4.472](https://academa.ai/lectures/edit-distance-dp-derivation?t=784.4723125): c22 is indicated — a transient flash. ##### [13:8.335](https://academa.ai/lectures/edit-distance-dp-derivation?t=788.3348125) Narration: From there, the one came from the diagonal again, but this time u and a were different, so the step cost one. That is a substitution. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid; c33 — a Math \[text\] that says "$1$" drawn in grid; c34 — a Math \[text\] that says "$2$" drawn in grid; answer\_math — a Math \[text\] that says "$D(3, 4) = 2$"; head\_back — a Heading that says "Walking the Arrows Backwards"; path\_1 — a Vector \[green\] drawn in grid (start=(4.5, -3.5), end=(3.5, -3.5), trim\_tip=True); path\_2 — a Vector \[green\] drawn in grid (start=(3.5, -3.5), end=(2.5, -2.5), trim\_tip=True) Actions: - [13:10.041](https://academa.ai/lectures/edit-distance-dp-derivation?t=790.0413125): path\_3 is shown on the screen, drawn. - [13:15.01](https://academa.ai/lectures/edit-distance-dp-derivation?t=795.0103125): c11 is indicated — a transient flash. ##### [13:16.667](https://academa.ai/lectures/edit-distance-dp-derivation?t=796.6668125) Narration: And the last diagonal step is another free match, s against s, and it lands us back in the empty corner. Four steps, one for each column of the alignment we drew at the very beginning. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid; c33 — a Math \[text\] that says "$1$" drawn in grid; c34 — a Math \[text\] that says "$2$" drawn in grid; answer\_math — a Math \[text\] that says "$D(3, 4) = 2$"; head\_back — a Heading that says "Walking the Arrows Backwards"; path\_1 — a Vector \[green\] drawn in grid (start=(4.5, -3.5), end=(3.5, -3.5), trim\_tip=True); path\_2 — a Vector \[green\] drawn in grid (start=(3.5, -3.5), end=(2.5, -2.5), trim\_tip=True); path\_3 — a Vector \[green\] drawn in grid (start=(2.5, -2.5), end=(1.5, -1.5), trim\_tip=True) Actions: - [13:21.276](https://academa.ai/lectures/edit-distance-dp-derivation?t=801.2763125): path\_4 is shown on the screen, drawn. - [13:22.529](https://academa.ai/lectures/edit-distance-dp-derivation?t=802.5293125000001): c00 is indicated — a transient flash. ##### [13:28.691](https://academa.ai/lectures/edit-distance-dp-derivation?t=808.6908125) Narration: Read that path forwards and you have the script. Match the s at the front. Substitute the u with an a. Match the n in the middle. Insert a d at the end. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid; c33 — a Math \[text\] that says "$1$" drawn in grid; c34 — a Math \[text\] that says "$2$" drawn in grid; answer\_math — a Math \[text\] that says "$D(3, 4) = 2$"; head\_back — a Heading that says "Walking the Arrows Backwards"; path\_1 — a Vector \[green\] drawn in grid (start=(4.5, -3.5), end=(3.5, -3.5), trim\_tip=True); path\_2 — a Vector \[green\] drawn in grid (start=(3.5, -3.5), end=(2.5, -2.5), trim\_tip=True); path\_3 — a Vector \[green\] drawn in grid (start=(2.5, -2.5), end=(1.5, -1.5), trim\_tip=True); path\_4 — a Vector \[green\] drawn in grid (start=(1.5, -1.5), end=(0.5, -0.5), trim\_tip=True) Actions: - [13:28.691](https://academa.ai/lectures/edit-distance-dp-derivation?t=808.6908125): script is shown on the screen, written out. - [13:32.998](https://academa.ai/lectures/edit-distance-dp-derivation?t=812.9983125000001): script (the "at the front" part) is emphasized. - [13:34.135](https://academa.ai/lectures/edit-distance-dp-derivation?t=814.1353125): script (the "Substitute the" part) is emphasized. - [13:34.135](https://academa.ai/lectures/edit-distance-dp-derivation?t=814.1353125): script (the "at the front" part) is no longer emphasized. - [13:37.653](https://academa.ai/lectures/edit-distance-dp-derivation?t=817.6533125000001): script (the "Substitute the" part) is no longer emphasized. - [13:37.653](https://academa.ai/lectures/edit-distance-dp-derivation?t=817.6533125000001): script (the "in the middle" part) is emphasized. - [13:38.733](https://academa.ai/lectures/edit-distance-dp-derivation?t=818.7333125): script (the "Insert a" part) is emphasized. - [13:38.733](https://academa.ai/lectures/edit-distance-dp-derivation?t=818.7333125): script (the "in the middle" part) is no longer emphasized. - [13:40.498](https://academa.ai/lectures/edit-distance-dp-derivation?t=820.4983125): script (the "Insert a" part) is no longer emphasized. ##### [13:41.098](https://academa.ai/lectures/edit-distance-dp-derivation?t=821.0983125) Narration: Two of those four steps are free, and the two that cost anything add up to two, which is the number sitting in the corner. So the table did not merely measure the distance. It constructed the edits. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid; c33 — a Math \[text\] that says "$1$" drawn in grid; c34 — a Math \[text\] that says "$2$" drawn in grid; answer\_math — a Math \[text\] that says "$D(3, 4) = 2$"; script — a Block \[text\] that says "Match the $s$ at the front. Free. Substitute the $u$ with an $a$. Cost one. Match the $n$ in the middle. Free. Insert a $d$ at the end. Cost one."; head\_back — a Heading that says "Walking the Arrows Backwards"; path\_1 — a Vector \[green\] drawn in grid (start=(4.5, -3.5), end=(3.5, -3.5), trim\_tip=True); path\_2 — a Vector \[green\] drawn in grid (start=(3.5, -3.5), end=(2.5, -2.5), trim\_tip=True); path\_3 — a Vector \[green\] drawn in grid (start=(2.5, -2.5), end=(1.5, -1.5), trim\_tip=True); path\_4 — a Vector \[green\] drawn in grid (start=(1.5, -1.5), end=(0.5, -0.5), trim\_tip=True) Actions: - [13:47.008](https://academa.ai/lectures/edit-distance-dp-derivation?t=827.0083125000001): answer\_math is indicated — a transient flash. - [13:52.906](https://academa.ai/lectures/edit-distance-dp-derivation?t=832.9058125): answer\_math is hidden from the screen — left the board. - [13:52.906](https://academa.ai/lectures/edit-distance-dp-derivation?t=832.9058125): head\_back is hidden from the screen — left the board. - [13:52.906](https://academa.ai/lectures/edit-distance-dp-derivation?t=832.9058125): script is hidden from the screen — left the board. ##### [13:54.106](https://academa.ai/lectures/edit-distance-dp-derivation?t=834.1058125) Narration: So what did all of that buy us? Twenty squares. Twenty subproblems, each one solved exactly once and then written down where the others can see it. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid; c33 — a Math \[text\] that says "$1$" drawn in grid; c34 — a Math \[text\] that says "$2$" drawn in grid; path\_1 — a Vector \[green\] drawn in grid (start=(4.5, -3.5), end=(3.5, -3.5), trim\_tip=True); path\_2 — a Vector \[green\] drawn in grid (start=(3.5, -3.5), end=(2.5, -2.5), trim\_tip=True); path\_3 — a Vector \[green\] drawn in grid (start=(2.5, -2.5), end=(1.5, -1.5), trim\_tip=True); path\_4 — a Vector \[green\] drawn in grid (start=(1.5, -1.5), end=(0.5, -0.5), trim\_tip=True) Actions: - [13:54.106](https://academa.ai/lectures/edit-distance-dp-derivation?t=834.1058125): head\_cost is shown on the screen, written out. - [13:56.149](https://academa.ai/lectures/edit-distance-dp-derivation?t=836.1493125000001): counts is shown on the screen, written out. - [14:0.073](https://academa.ai/lectures/edit-distance-dp-derivation?t=840.0733125000002): counts is shown on the screen, written out. ##### [14:3.622](https://academa.ai/lectures/edit-distance-dp-derivation?t=843.6223125) Narration: The plain recursion from earlier, run to completion on these same two short words, makes a hundred and ninety three calls. Same answer, nearly ten times the work, and the extra nine tenths of it is the same handful of subproblems being recomputed. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid; c33 — a Math \[text\] that says "$1$" drawn in grid; c34 — a Math \[text\] that says "$2$" drawn in grid; path\_1 — a Vector \[green\] drawn in grid (start=(4.5, -3.5), end=(3.5, -3.5), trim\_tip=True); path\_2 — a Vector \[green\] drawn in grid (start=(3.5, -3.5), end=(2.5, -2.5), trim\_tip=True); path\_3 — a Vector \[green\] drawn in grid (start=(2.5, -2.5), end=(1.5, -1.5), trim\_tip=True); path\_4 — a Vector \[green\] drawn in grid (start=(1.5, -1.5), end=(0.5, -0.5), trim\_tip=True); head\_cost — a Heading that says "What the Table Bought" Actions: - [14:8.881](https://academa.ai/lectures/edit-distance-dp-derivation?t=848.8813125000001): counts (the "193" part) is emphasized. - [14:12.108](https://academa.ai/lectures/edit-distance-dp-derivation?t=852.1083125000001): counts (the "193" part) is no longer emphasized. ##### [14:18.2](https://academa.ai/lectures/edit-distance-dp-derivation?t=858.1998125) Narration: And it gets worse very fast. Take kitten and sitting, which is the standard example. The table has fifty six squares in it. The recursion makes nearly thirty thousand calls. Board: Unchanged from the preceding beat in this scene. Actions: - [14:25.049](https://academa.ai/lectures/edit-distance-dp-derivation?t=865.0493125): counts is shown on the screen, written out. - [14:27.998](https://academa.ai/lectures/edit-distance-dp-derivation?t=867.9983125000001): counts (the "29,737" part) is emphasized. - [14:29.473](https://academa.ai/lectures/edit-distance-dp-derivation?t=869.4728125): counts (the "29,737" part) is no longer emphasized. ##### [14:30.073](https://academa.ai/lectures/edit-distance-dp-derivation?t=870.0728125) Narration: The table is m plus one times n plus one, always, no matter what the words are. The recursion is exponential in the length of the words. That gap is the whole of what dynamic programming buys you, and it is bought with a grid you could draw on a napkin. Board: Unchanged from the preceding beat in this scene. Actions: - [14:32.941](https://academa.ai/lectures/edit-distance-dp-derivation?t=872.9413125000001): complexity is shown on the screen, written out. - [14:44.365](https://academa.ai/lectures/edit-distance-dp-derivation?t=884.3653125000001): complexity is indicated — a transient flash. ##### [14:45.894](https://academa.ai/lectures/edit-distance-dp-derivation?t=885.8943125000001) Narration: And notice that nothing in that argument was about spelling. Strip the two words out of it and what is left is a procedure. Board: grid — a Figure (x\_range=(-1.2, 5.4), y\_range=(-4.4, 1.2), aspect=(6.6, 5.6)); rules — a Gridlines \[gray\] drawn in grid (x\_range=(0.0, 5.0), y\_range=(-4.0, 0.0), step=1.0); side\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; side\_u — a Math \[green\] that says "$upright("u")$" drawn in grid; side\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_s — a Math \[green\] that says "$upright("s")$" drawn in grid; top\_a — a Math \[green\] that says "$upright("a")$" drawn in grid; top\_n — a Math \[green\] that says "$upright("n")$" drawn in grid; top\_d — a Math \[green\] that says "$upright("d")$" drawn in grid; c00 — a Math \[gray\] that says "$0$" drawn in grid; c01 — a Math \[gray\] that says "$1$" drawn in grid; c02 — a Math \[gray\] that says "$2$" drawn in grid; c03 — a Math \[gray\] that says "$3$" drawn in grid; c04 — a Math \[gray\] that says "$4$" drawn in grid; c10 — a Math \[gray\] that says "$1$" drawn in grid; c20 — a Math \[gray\] that says "$2$" drawn in grid; c30 — a Math \[gray\] that says "$3$" drawn in grid; c11 — a Math \[text\] that says "$0$" drawn in grid; c12 — a Math \[text\] that says "$1$" drawn in grid; c13 — a Math \[text\] that says "$2$" drawn in grid; c14 — a Math \[text\] that says "$3$" drawn in grid; c21 — a Math \[text\] that says "$1$" drawn in grid; c22 — a Math \[text\] that says "$1$" drawn in grid; c23 — a Math \[text\] that says "$2$" drawn in grid; c24 — a Math \[text\] that says "$3$" drawn in grid; c31 — a Math \[text\] that says "$2$" drawn in grid; c32 — a Math \[text\] that says "$2$" drawn in grid; c33 — a Math \[text\] that says "$1$" drawn in grid; c34 — a Math \[text\] that says "$2$" drawn in grid; path\_1 — a Vector \[green\] drawn in grid (start=(4.5, -3.5), end=(3.5, -3.5), trim\_tip=True); path\_2 — a Vector \[green\] drawn in grid (start=(3.5, -3.5), end=(2.5, -2.5), trim\_tip=True); path\_3 — a Vector \[green\] drawn in grid (start=(2.5, -2.5), end=(1.5, -1.5), trim\_tip=True); path\_4 — a Vector \[green\] drawn in grid (start=(1.5, -1.5), end=(0.5, -0.5), trim\_tip=True); complexity — a Math \[text\] that says "$(m + 1)(n + 1) quad upright("cells, always")$"; head\_cost — a Heading that says "What the Table Bought" Actions: - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): complexity is hidden from the screen — left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): counts is hidden from the screen — left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): grid is hidden from the screen — left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): rules is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): side\_s is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): side\_u is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): side\_n is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): top\_s is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): top\_a is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): top\_n is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): top\_d is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c00 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c01 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c02 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c03 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c04 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c10 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c20 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c30 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c11 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c12 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c13 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c14 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c21 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c22 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c23 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c24 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c31 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c32 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c33 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): c34 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): path\_1 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): path\_2 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): path\_3 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): path\_4 is hidden from the screen — grid left the board. - [14:52.675](https://academa.ai/lectures/edit-distance-dp-derivation?t=892.6748125): head\_cost is hidden from the screen — left the board. ##### [14:53.875](https://academa.ai/lectures/edit-distance-dp-derivation?t=893.8748125) Narration: Name the subproblem in one sentence. If you cannot say it in one sentence you do not have it yet, and no amount of staring at a table will rescue you. Board: Empty. Actions: - [14:53.875](https://academa.ai/lectures/edit-distance-dp-derivation?t=893.8748125): head\_method is shown on the screen, written out. - [14:53.875](https://academa.ai/lectures/edit-distance-dp-derivation?t=893.8748125): method is shown on the screen, written out. - [14:56.8](https://academa.ai/lectures/edit-distance-dp-derivation?t=896.8003125): method (the "Name the subproblem" part) is emphasized. ##### [15:2.834](https://academa.ai/lectures/edit-distance-dp-derivation?t=902.8338125) Narration: Ask what the last decision could have been. Not the first one, the last one, because the last one is what leaves a smaller version of the same problem behind it. Then let each answer point at that smaller version. Board: method — a Block \[text\] that says "Name the subproblem in one sentence. Ask what the last decision could have been. Let each answer point at a smaller subproblem. Write down the cases the rule cannot reach. Fill in an order that has every dependency ready."; head\_method — a Heading that says "The Method, Without the Example" Actions: - [15:3.182](https://academa.ai/lectures/edit-distance-dp-derivation?t=903.1823125000001): method (the "Ask what the last decision" part) is emphasized. - [15:3.182](https://academa.ai/lectures/edit-distance-dp-derivation?t=903.1823125000001): method (the "Name the subproblem" part) is no longer emphasized. - [15:13.55](https://academa.ai/lectures/edit-distance-dp-derivation?t=913.5503125): method (the "Ask what the last decision" part) is no longer emphasized. - [15:13.55](https://academa.ai/lectures/edit-distance-dp-derivation?t=913.5503125): method (the "Let each answer point" part) is emphasized. ##### [15:16.228](https://academa.ai/lectures/edit-distance-dp-derivation?t=916.2283125) Narration: Write down the cases the rule cannot reach, which are almost always the empty ones. And then fill the thing in in an order where everything a square needs is already there. For us that was left to right and top to bottom, because every arrow pointed up or left. Board: Unchanged from the preceding beat in this scene. Actions: - [15:16.785](https://academa.ai/lectures/edit-distance-dp-derivation?t=916.7853125000001): method (the "Let each answer point" part) is no longer emphasized. - [15:16.785](https://academa.ai/lectures/edit-distance-dp-derivation?t=916.7853125000001): method (the "Write down the cases" part) is emphasized. - [15:21.58](https://academa.ai/lectures/edit-distance-dp-derivation?t=921.5803125): method (the "Fill in an order" part) is emphasized. - [15:21.58](https://academa.ai/lectures/edit-distance-dp-derivation?t=921.5803125): method (the "Write down the cases" part) is no longer emphasized. - [15:30.764](https://academa.ai/lectures/edit-distance-dp-derivation?t=930.7638125000001): method (the "Fill in an order" part) is no longer emphasized. ##### [15:31.364](https://academa.ai/lectures/edit-distance-dp-derivation?t=931.3638125) Narration: Five steps, and not one of them mentioned edit distance. The next time you meet one of these, do not go looking for the solution you memorised. Go and find the sentence. Board: Unchanged from the preceding beat in this scene. Actions: - [15:40.442](https://academa.ai/lectures/edit-distance-dp-derivation?t=940.4423125000001): method (the "one sentence" part) is indicated — a transient flash. - [15:41.46](https://academa.ai/lectures/edit-distance-dp-derivation?t=941.4602708333333): head\_method is hidden from the screen — left the board. - [15:41.46](https://academa.ai/lectures/edit-distance-dp-derivation?t=941.4602708333333): method is hidden from the screen — left the board.