WEBVTT 00:00:00.058 --> 00:00:04.285 Dynamic programming is usually taught as a list of solutions to memorise. 00:00:04.481 --> 00:00:06.189 I want to do the opposite. 00:00:06.385 --> 00:00:10.540 Over the next twenty minutes we are going to derive one, from a problem statement, 00:00:10.623 --> 00:00:12.516 with nothing remembered at all. 00:00:12.713 --> 00:00:17.346 The problem is edit distance, and what falls out of it is the method itself. 00:00:18.742 --> 00:00:20.215 So, two words. 00:00:20.298 --> 00:00:23.492 The source word is s u n, sun. 00:00:23.595 --> 00:00:26.754 The target word is s a n d, sand. 00:00:26.951 --> 00:00:31.153 You are allowed to change the source one character at a time until it reads like 00:00:31.153 --> 00:00:35.368 the target, and the question is how few changes that takes. 00:00:36.420 --> 00:00:39.207 Three moves are allowed, and only three. 00:00:39.404 --> 00:00:43.515 You can insert a character anywhere in the word. You can delete one. 00:00:43.711 --> 00:00:45.383 Or you can substitute one character 00:00:45.383 --> 00:00:49.691 for another, which is the only one of the three that leaves the length alone. 00:00:50.487 --> 00:00:53.205 Here is one way to get from one to the other. 00:00:53.402 --> 00:00:56.883 The s at the front already matches, so leave it alone. 00:00:56.966 --> 00:01:01.109 The u has to become an a, and that is one substitution. 00:01:01.192 --> 00:01:03.457 The n already matches too. 00:01:03.561 --> 00:01:07.311 And then there is a d hanging off the end of the target with nothing above it, 00:01:07.311 --> 00:01:08.600 so insert it. 00:01:09.397 --> 00:01:11.046 Look at the shape of that. 00:01:11.359 --> 00:01:15.156 Four columns, and the source only has three characters in it. 00:01:15.353 --> 00:01:17.768 That is exactly what an insertion is: 00:01:17.872 --> 00:01:21.855 a column with a target character in it and nothing standing above. 00:01:22.168 --> 00:01:26.313 Two edits in total, because two of the four columns cost nothing. 00:01:27.110 --> 00:01:29.709 Two is not obviously the smallest, though. 00:01:29.792 --> 00:01:33.124 Written out, that route is sun to san to sand. 00:01:33.228 --> 00:01:35.156 And here is a clumsier one: 00:01:35.352 --> 00:01:40.334 delete the u to get s n, insert an a, insert a d. 00:01:40.530 --> 00:01:43.051 Three edits, same destination. 00:01:43.363 --> 00:01:46.844 The edit distance is the minimum over every possible route, 00:01:46.927 --> 00:01:49.192 and there are a great many routes. 00:01:49.733 --> 00:01:52.404 Which means we are not going to enumerate them. 00:01:52.601 --> 00:01:55.792 We need to break the problem into smaller copies of itself, 00:01:55.875 --> 00:01:59.380 and that is the move that starts every dynamic program there is. 00:01:59.463 --> 00:02:01.948 Not a table. A sentence. 00:02:03.344 --> 00:02:06.724 Here is that sentence, and it is worth saying slowly. 00:02:06.921 --> 00:02:10.984 D of i and j is the edit distance between the first i characters 00:02:10.984 --> 00:02:15.095 of the source word and the first j characters of the target word. 00:02:15.709 --> 00:02:18.055 That is the entire definition. 00:02:18.852 --> 00:02:21.337 Prefixes, in other words. 00:02:21.650 --> 00:02:26.318 Not arbitrary pieces of the words, not suffixes, not substrings. 00:02:26.933 --> 00:02:30.951 Just: how much of each word have I dealt with so far? 00:02:31.147 --> 00:02:32.401 Sun has three characters 00:02:32.401 --> 00:02:37.324 and sand has four, so the answer to the original question is one single value. 00:02:38.028 --> 00:02:41.233 And choosing prefixes is a real choice, by the way. 00:02:41.337 --> 00:02:43.774 It is the choice that does all of the work here, 00:02:43.857 --> 00:02:47.373 and if you pick the wrong subproblem the rule will not close up on itself 00:02:47.456 --> 00:02:50.254 and you will have to come back and pick another one. 00:02:50.567 --> 00:02:52.286 Expect that to happen. 00:02:53.683 --> 00:02:58.176 Now suppose you code that definition up recursively, the obvious way. 00:02:58.373 --> 00:03:01.750 To compute D of three and four you try all three moves, 00:03:01.833 --> 00:03:05.607 and each one hands you back a smaller pair of prefixes to solve. 00:03:06.403 --> 00:03:09.072 Deleting gives you D of two, four. 00:03:09.155 --> 00:03:11.710 Inserting gives D of three, three. 00:03:11.814 --> 00:03:14.984 Substituting gives D of two, three. 00:03:15.436 --> 00:03:19.779 Three calls, every one of them strictly smaller than the thing we started with. 00:03:20.692 --> 00:03:24.953 Expand one more level and each of those three splits into three again. 00:03:25.150 --> 00:03:28.355 Nine calls, and we have only gone two deep. 00:03:29.151 --> 00:03:32.508 Now look carefully at what is actually written down there. 00:03:32.704 --> 00:03:34.992 D of two, three is here. 00:03:35.189 --> 00:03:36.350 And here. 00:03:36.547 --> 00:03:37.987 And again here. 00:03:38.439 --> 00:03:42.770 Three copies of one subproblem, and each copy is about to go off and compute 00:03:42.770 --> 00:03:47.311 the same number from scratch, knowing nothing whatsoever about the other two. 00:03:48.107 --> 00:03:52.102 That is the whole disease, and it is worth being precise about it. 00:03:52.298 --> 00:03:54.038 The recursion is correct. 00:03:54.121 --> 00:03:57.674 It is simply doing the same work over and over because it has no memory 00:03:57.674 --> 00:03:59.730 of what it has already worked out. 00:04:00.182 --> 00:04:03.154 Right at the end we will count exactly how much. 00:04:03.580 --> 00:04:05.519 So we have a subproblem. 00:04:05.832 --> 00:04:10.497 What we do not have yet is the rule that ties one subproblem to the smaller ones, 00:04:10.580 --> 00:04:14.261 and that rule comes out of a single question about the last character. 00:04:15.362 --> 00:04:17.890 The rule always comes out of the same question, 00:04:17.974 --> 00:04:20.250 whatever the problem happens to be. 00:04:20.447 --> 00:04:25.138 Look at the very end of both prefixes, and ask what the last step was. 00:04:26.051 --> 00:04:29.778 These four squares are a corner of the table we are about to build. 00:04:29.975 --> 00:04:34.550 The one at the bottom right is the cell we want, D of i and j. 00:04:34.862 --> 00:04:38.300 The other three are all strictly smaller subproblems: 00:04:38.496 --> 00:04:42.305 one row up, one column to the left, and one of each. 00:04:43.009 --> 00:04:47.259 Suppose the last edit deleted the source character A sub i. 00:04:47.572 --> 00:04:49.252 Then that character is gone, 00:04:49.336 --> 00:04:53.806 it was matched against nothing at all, and what is left over is the first i minus one 00:04:53.806 --> 00:04:57.650 characters of the source against the whole first j of the target. 00:04:57.754 --> 00:05:02.306 That is the cell directly above, plus one for the deletion itself. 00:05:03.102 --> 00:05:08.281 Suppose instead that the last edit inserted the target character B sub j. 00:05:08.896 --> 00:05:10.727 Now the source is untouched, 00:05:10.811 --> 00:05:14.806 and it is the target that has one fewer character left to account for. 00:05:15.421 --> 00:05:19.554 That is the cell immediately to the left, plus one for the insertion. 00:05:19.979 --> 00:05:22.995 And the third possibility is that A sub i 00:05:23.079 --> 00:05:26.656 and B sub j were simply lined up against each other. 00:05:26.760 --> 00:05:31.010 Both prefixes lose a character, so we arrive from the diagonal. 00:05:31.206 --> 00:05:35.178 What that step costs depends entirely on the two characters. 00:05:35.975 --> 00:05:40.318 That case is worth pausing on, because it is doing two jobs at once. 00:05:40.514 --> 00:05:45.519 When the two characters already agree, it is a match and it costs nothing at all. 00:05:45.715 --> 00:05:49.675 When they disagree, it is a substitution and it costs one. 00:05:49.872 --> 00:05:53.413 Same arrow, same neighbour, two different prices. 00:05:54.465 --> 00:05:56.057 Make that concrete. 00:05:56.253 --> 00:06:02.152 Take i equals two and j equals two, so the prefixes are s u and s a. 00:06:02.349 --> 00:06:04.962 The last characters are u and a. 00:06:05.158 --> 00:06:07.341 They are different, so that diagonal step 00:06:07.341 --> 00:06:12.845 costs one, sitting on top of whatever the distance between s and s turned out to be. 00:06:13.757 --> 00:06:16.045 Call that extra cost c. 00:06:16.242 --> 00:06:20.387 Zero when the two characters agree, one when they do not. 00:06:20.584 --> 00:06:25.043 That single letter is the only place the actual words enter the arithmetic. 00:06:25.355 --> 00:06:28.793 Everything else in the rule is pure bookkeeping. 00:06:29.589 --> 00:06:34.443 Three cases, three neighbours, and no fourth possibility anywhere. 00:06:34.895 --> 00:06:37.853 Any edit sequence at all has to end in one of those three, 00:06:37.937 --> 00:06:41.421 so the cheapest sequence ends in whichever of the three is cheapest. 00:06:42.817 --> 00:06:44.579 So there is the recurrence, 00:06:44.663 --> 00:06:48.275 and notice that we did not guess it and we did not remember it. 00:06:48.588 --> 00:06:50.201 It is nothing more than the minimum 00:06:50.201 --> 00:06:53.012 over the three ways the last step could have gone. 00:06:53.808 --> 00:06:56.572 Read it as a picture rather than as algebra. 00:06:56.769 --> 00:06:58.778 One plus the cell above. 00:06:58.975 --> 00:07:01.216 One plus the cell to the left. 00:07:01.529 --> 00:07:04.374 Or c plus the cell on the diagonal. 00:07:04.989 --> 00:07:08.832 Take whichever of those three is smallest, and that is your answer. 00:07:09.629 --> 00:07:12.636 And here is the cost, spelled out properly. 00:07:13.088 --> 00:07:15.907 c is zero if the character at position i 00:07:15.991 --> 00:07:20.833 and the character at position j are the same, and one if they are not. 00:07:21.746 --> 00:07:23.697 There is a hole in this, though. 00:07:24.149 --> 00:07:28.131 Every one of those three cases points at a smaller cell, which is perfectly fine 00:07:28.131 --> 00:07:31.569 right up until the moment there is no smaller cell to point at. 00:07:31.881 --> 00:07:34.460 The recurrence cannot start itself. 00:07:35.256 --> 00:07:38.995 So we also need the cases that are true with no recursion at all. 00:07:39.099 --> 00:07:40.722 Those turn out to be the easy part, 00:07:40.806 --> 00:07:44.390 because a prefix of length zero is just the empty word. 00:07:44.474 --> 00:07:47.157 And that is where the table finally comes in. 00:07:48.300 --> 00:07:50.425 Here is the table. Four rows, 00:07:50.425 --> 00:07:55.151 because sun has three characters and we need a row for zero characters as well. 00:07:55.463 --> 00:07:58.796 Five columns, for the same reason, with sand. 00:08:00.011 --> 00:08:03.007 Every single square in it is one subproblem. 00:08:03.111 --> 00:08:07.393 The square in row i and column j is going to hold D of i and j, 00:08:07.476 --> 00:08:11.366 and the one we actually want is down there in the bottom right corner. 00:08:12.070 --> 00:08:13.845 Start with row zero. 00:08:13.928 --> 00:08:18.851 That row is the source prefix of length zero, which is the empty word. 00:08:19.048 --> 00:08:23.285 Turning the empty word into the first j characters of sand costs exactly j 00:08:23.285 --> 00:08:27.895 insertions, one per character, so row zero simply counts up. 00:08:28.092 --> 00:08:31.157 Zero, one, two, three, four. 00:08:31.954 --> 00:08:34.799 Column zero is the mirror image of that. 00:08:34.903 --> 00:08:39.533 Turning the first i characters of sun into the empty word costs i deletions, 00:08:39.616 --> 00:08:41.626 so it counts down the side. 00:08:41.822 --> 00:08:43.565 One, two, three. 00:08:44.477 --> 00:08:48.623 Those eight squares are true by definition rather than by any rule. 00:08:48.819 --> 00:08:50.527 And look at the corner one: 00:08:50.979 --> 00:08:55.252 no characters against no characters, nothing to do, zero. 00:08:56.049 --> 00:08:58.578 Everything else comes from the rule we derived, 00:08:58.661 --> 00:09:01.831 and the three ways in keep the three colours from before: 00:09:02.028 --> 00:09:06.231 red from above, blue from the left, yellow from the diagonal. 00:09:06.428 --> 00:09:07.843 Twelve squares left, 00:09:07.926 --> 00:09:12.048 and each one is the smallest of three numbers already sitting on the page. 00:09:12.845 --> 00:09:16.561 Take the first empty one, row one, column one. 00:09:17.013 --> 00:09:23.004 Row one means the source prefix is s. Column one means the target prefix is s. 00:09:23.201 --> 00:09:26.763 Three arrows point into that square, one from each neighbour, 00:09:26.846 --> 00:09:30.399 and the square holds the smallest of what those three arrows offer. 00:09:31.312 --> 00:09:36.479 From above, the neighbour holds one, and a deletion costs one more, so two. 00:09:36.931 --> 00:09:41.506 From the left, one again, plus one for an insertion, so two again. 00:09:41.958 --> 00:09:47.158 From the diagonal, zero, and both characters here are s, so c is zero 00:09:47.241 --> 00:09:50.087 and the diagonal asks for nothing extra. 00:09:50.790 --> 00:09:55.296 Zero wins, so the square is zero, and that is exactly right. 00:09:55.492 --> 00:09:58.512 Turning s into s costs nothing at all. 00:09:59.308 --> 00:10:02.235 Now slide the arrows one column to the right. 00:10:02.339 --> 00:10:04.743 Row one is still just s. 00:10:04.928 --> 00:10:07.042 Column two is s a. 00:10:07.227 --> 00:10:09.027 From above, three. 00:10:09.212 --> 00:10:10.722 From the left, one. 00:10:10.907 --> 00:10:12.682 From the diagonal, one, 00:10:12.765 --> 00:10:17.827 and this time the characters are s and a, which differ, so add one and you get two. 00:10:18.012 --> 00:10:19.685 The smallest is one. 00:10:19.994 --> 00:10:25.078 One insertion. Build s a out of a single s by adding an a on the end. 00:10:25.161 --> 00:10:28.714 The table just derived that on its own, and it will keep doing it. 00:10:29.511 --> 00:10:35.003 The rest of that row goes the same way. Column three, two. Column four, three. 00:10:35.107 --> 00:10:39.528 Row one now reads one, zero, one, two, three, 00:10:39.611 --> 00:10:43.013 and each of those is the cost of building a longer and longer prefix 00:10:43.013 --> 00:10:45.034 of sand out of one s. 00:10:45.947 --> 00:10:49.431 Row two now, so the source prefix is s u. 00:10:49.743 --> 00:10:52.937 Back to column one, where the target is s. 00:10:53.133 --> 00:10:55.758 From above, zero plus one is one. 00:10:55.954 --> 00:10:58.591 From the left, two plus one is three. 00:10:58.787 --> 00:11:03.571 From the diagonal, one plus one is two, because u and s are different. 00:11:04.023 --> 00:11:05.336 One wins. 00:11:06.133 --> 00:11:08.502 And notice which arrow it came from. 00:11:08.698 --> 00:11:12.298 The one from above, the red one, which is a deletion. 00:11:12.495 --> 00:11:18.022 Turning s u into s means throwing the u away, and the table found that by itself. 00:11:18.772 --> 00:11:21.118 This next one is the interesting square. 00:11:21.384 --> 00:11:23.568 Row two, column two: 00:11:23.729 --> 00:11:25.667 s u against s a. 00:11:25.750 --> 00:11:27.457 From above, two. 00:11:27.619 --> 00:11:29.315 From the left, two. 00:11:29.476 --> 00:11:33.459 From the diagonal, zero plus one, because u and a differ. 00:11:33.772 --> 00:11:36.396 One, from the diagonal, and that diagonal 00:11:36.396 --> 00:11:40.750 step is exactly the substitution we spotted by eye at the very start. 00:11:41.547 --> 00:11:42.883 Finish the row. 00:11:43.079 --> 00:11:44.949 Column three gives two. 00:11:45.053 --> 00:11:47.155 Column four gives three. 00:11:47.352 --> 00:11:51.323 Nothing matches anywhere along there, so every step is costing something. 00:11:52.119 --> 00:11:55.975 Last row, so the source is the whole word, s u n. 00:11:56.078 --> 00:11:57.972 Column one gives two. 00:11:58.168 --> 00:12:00.340 Column two gives two as well. 00:12:01.137 --> 00:12:04.121 Column three is worth slowing down for. 00:12:04.318 --> 00:12:10.643 Source s u n, target s a n. The last characters are both n, so c is zero, 00:12:10.726 --> 00:12:13.488 and the diagonal offers one plus nothing. 00:12:13.571 --> 00:12:18.297 Above offers three, the left offers three, the diagonal offers one. 00:12:18.447 --> 00:12:20.096 The number drops. 00:12:20.963 --> 00:12:23.585 That is a free match paying for itself. 00:12:23.668 --> 00:12:25.640 And now the very last square. 00:12:25.723 --> 00:12:29.392 Source s u n, target s a n d. 00:12:29.995 --> 00:12:35.163 The last characters are n and d, which differ. Above gives four. 00:12:35.255 --> 00:12:37.122 The diagonal gives three. 00:12:37.205 --> 00:12:40.329 And from the left, one plus one is two. 00:12:41.126 --> 00:12:42.090 Two. 00:12:42.287 --> 00:12:45.617 That is the edit distance between sun and sand, 00:12:45.700 --> 00:12:49.320 and every one of those twenty numbers was worked out exactly once, 00:12:49.403 --> 00:12:52.678 from numbers already sitting above it and to its left. 00:12:54.191 --> 00:12:57.744 Now the number on its own is not really the interesting part. 00:12:57.848 --> 00:13:01.517 The table also knows which moves it used to get there, and we can read them 00:13:01.517 --> 00:13:04.792 back out by walking the winning arrows backwards from the corner. 00:13:05.704 --> 00:13:07.165 Start at the bottom right. 00:13:07.248 --> 00:13:10.277 The two there came from the left neighbour, which held one. 00:13:10.360 --> 00:13:14.795 A step from the left is an insertion, so the last edit was inserting the d. 00:13:15.592 --> 00:13:19.737 From that square, the one came from the diagonal, and the characters there were n 00:13:19.737 --> 00:13:22.974 and n, equal, so the step cost nothing. 00:13:23.057 --> 00:13:25.470 A free diagonal step is a match. 00:13:25.553 --> 00:13:27.934 Keep the n exactly as it is. 00:13:28.638 --> 00:13:31.214 From there, the one came from the diagonal again, 00:13:31.297 --> 00:13:34.583 but this time u and a were different, so the step cost one. 00:13:34.780 --> 00:13:36.696 That is a substitution. 00:13:37.493 --> 00:13:41.148 And the last diagonal step is another free match, s against s, 00:13:41.231 --> 00:13:43.681 and it lands us back in the empty corner. 00:13:43.878 --> 00:13:48.430 Four steps, one for each column of the alignment we drew at the very beginning. 00:13:49.226 --> 00:13:52.106 Read that path forwards and you have the script. 00:13:52.303 --> 00:13:54.161 Match the s at the front. 00:13:54.358 --> 00:13:56.541 Substitute the u with an a. 00:13:56.738 --> 00:13:58.620 Match the n in the middle. 00:13:58.816 --> 00:14:00.652 Insert a d at the end. 00:14:01.564 --> 00:14:06.195 Two of those four steps are free, and the two that cost anything add up to two, 00:14:06.278 --> 00:14:08.543 which is the number sitting in the corner. 00:14:08.739 --> 00:14:13.581 So the table did not merely measure the distance. It constructed the edits. 00:14:15.094 --> 00:14:17.173 So what did all of that buy us? 00:14:17.485 --> 00:14:20.108 Twenty squares. Twenty subproblems, 00:14:20.191 --> 00:14:24.615 each one solved exactly once and then written down where the others can see it. 00:14:25.829 --> 00:14:30.564 The plain recursion from earlier, run to completion on these same two short words, 00:14:30.647 --> 00:14:32.923 makes a hundred and ninety three calls. 00:14:33.120 --> 00:14:37.195 Same answer, nearly ten times the work, and the extra nine tenths 00:14:37.195 --> 00:14:40.737 of it is the same handful of subproblems being recomputed. 00:14:41.348 --> 00:14:43.613 And it gets worse very fast. 00:14:43.809 --> 00:14:46.957 Take kitten and sitting, which is the standard example. 00:14:47.153 --> 00:14:49.778 The table has fifty six squares in it. 00:14:49.975 --> 00:14:52.773 The recursion makes nearly thirty thousand calls. 00:14:53.477 --> 00:14:58.468 The table is m plus one times n plus one, always, no matter what the words are. 00:14:58.551 --> 00:15:01.895 The recursion is exponential in the length of the words. 00:15:01.999 --> 00:15:05.433 That gap is the whole of what dynamic programming buys you, 00:15:05.516 --> 00:15:08.629 and it is bought with a grid you could draw on a napkin. 00:15:09.541 --> 00:15:13.014 And notice that nothing in that argument was about spelling. 00:15:13.326 --> 00:15:16.706 Strip the two words out of it and what is left is a procedure. 00:15:17.847 --> 00:15:20.576 Name the subproblem in one sentence. 00:15:20.773 --> 00:15:23.894 If you cannot say it in one sentence you do not have it yet, 00:15:23.977 --> 00:15:26.985 and no amount of staring at a table will rescue you. 00:15:27.526 --> 00:15:29.998 Ask what the last decision could have been. 00:15:30.081 --> 00:15:34.330 Not the first one, the last one, because the last one is what leaves a smaller 00:15:34.330 --> 00:15:36.641 version of the same problem behind it. 00:15:36.745 --> 00:15:39.962 Then let each answer point at that smaller version. 00:15:40.665 --> 00:15:42.986 Write down the cases the rule cannot reach, 00:15:43.069 --> 00:15:45.542 which are almost always the empty ones. 00:15:45.739 --> 00:15:46.796 And then fill the thing 00:15:46.796 --> 00:15:50.419 in in an order where everything a square needs is already there. 00:15:50.615 --> 00:15:53.156 For us that was left to right and top to bottom, 00:15:53.239 --> 00:15:56.061 because every arrow pointed up or left. 00:15:56.858 --> 00:16:00.586 Five steps, and not one of them mentioned edit distance. 00:16:01.386 --> 00:16:02.826 The next time you meet one of these, 00:16:02.826 --> 00:16:07.331 do not go looking for the solution you memorised. Go and find the sentence.