Welcome, in this video I will teach you about dynamic programming, we will go through one example. But once you understand that, you'll be able to apply dynamic programming to anything. So you start by laying out the problem like this, where you have the source wordplay here down the left column. And then, the targets were to transform into stay along the top row here and an empty string placeholder. Represented by the hashtag symbol at the start of each string here. The reason for this, will make more sense in the steps ahead. There are also some row and column in this easier, just to make things a bit easier to follow along. Now, the goal is to fill out this distance matrix D. Such that the element D 2, 3 for example, refers to the minimum at a distance from pl to sta. Which is the first two letters of the word play, to the first three letters of the target words stay. Or more generally for any element in the matrix by using this formula for the element at row i and column j. Being i equals two and j equal three, in the example, pl to sta. From the previous few slides, you know, each D of ij will be the minimum at the distance. Between the beginning of the source word to index i at the beginning of the targets word to index j. So that's for a source of length m and a target of length n, when you get to the bottom right corner D of mn. You have the minimum edit distance between the two strings. You will compute this from the shortest sub strength to the full strength that is. Starting with the shortest string in the top left corner and working down then to the right. The intuition is that you can build upon each sub problem by combining solutions. For example finding the minimum edit distance between two letters is easy. Then, you increase the problem size one letter at a time, building on what you already know. If this seems confusing at first, don't worry, it is but it will start to make more sense as you work through the examples. But first before you get started, recall the cost for each edit, one for insert and delete and two for replace. Okay, so the first step is to transform the source empty string, enter the target's empty string. The edit distance between the source empty string and the target empty string is zero. There is no formula here, it's just a special case so far, so good. Okay, to change nothing to nothing, you do nothing, good. Then you can move on to p to empty string and you can do this where they do it at its operation at the cost of one. Then empty string to s, which you can do with an insert at this operation at the cost of one. Now look at b two s, there is more than one possible way to make this transformation. Each possible sequence of edits is known as a path starting with b, you can insert s on the end to get ps. Then though is b from the beginning to get s, this has a cost of one inserts and one delete. At this point, notice that you've already calculated the cost of inserting a letter s. It's found in this red box here on top, when you calculate how to get from empty string to s. So you actually just calculate the cost of deleting the p and added onto the cost that you've stored in the red box above. This is one plus one equals two, in the second possible path, starting with p. You can delete b to get hashtag and then insert s to get s, notice again that you've already calculated the cost of the deleting p. In this blue box in the left, the blue box is the cost of going from p to hashtag by the deleting p. So you can calculate the cost of inserting p and added to the cost that you've stored in the blue box on the left. This is one plus one equals two, the third way is to replace p with s, so that you go from p to s and one step at the cost of two. For replacement, visually you can think of going from this green box and jumping directly into the orange box. The green box is the cost of not doing any edit which is zero, a replacement has a cost of two, so zero plus two equals two. Then, you take the minimum of all three of these paths, which is a two in this case. Then place that value in the cell, which gives you the minimum at a distance from p to s. So working off what you've already filled out, you'll notice that to fill in the cell. You need to know the cell above, to the left and adjacent upper left, shown in red, blue and green here. In doing so, you can benefit from some calculations already performed. Soon, I'll show you how to generalize this in a formula to fill out the rest of the matrix. But first, I will show you how to fill out the first column and the first row. So that every cell remaining has its own red, blue and green cells available as dependencies. This is what's coming up next. In this video, you learned about the cost of each operation, insert and deleting is one and then, replacing is two. You also saw how you can populate your table, in the next video, you will learn about a much faster way to populate your table
