Longest Common Subsequence (Dynamic Programming)

hey guys this is my dynamic programming tutorial with the longest common subsequence problem as our example now let me explain what the longest common subsequence problem is we have two strings let's call it P and Q and we're trying to find the common string and we're trying to find the longest one of course and in this case that would be b a d and one thing to note here is that these characters are not necessarily contigous we're going to solve this problem using dynamic programming but let's first talk about this General procedure that we have uh that we can use for solving any dynamic programming problems so the first step is to come up with a recursive solution and then we memorize the intermediate results or restore the intermediate results to make it run faster and finally we can come up with something called a bottom up approach and I'm going to explain what it means later this is an optional step by the way here's a recursive solution we're going to write this function LCS longest common sub sequence of p 0 and q0 the two input strings and we're going to return the length of the longest common subsequence instead of the subsequence itself so with our previous example we're going to return instead of b a d we're going to return the length of it which is three the idea behind any recursion is that of course we're going to take down this problem into smaller problems and we're going to solve those instead and there are two cases we need to consider for that the first case is when p 0 and q0 and with the same character let's call let's just call it X and there are some preceding characters let's call them P1 and q1 they could be any links they could be empty or non empty what we say this case is that the longest common subsequence of p 0 and q0 must end with x and so we'll get rid of these and we'll find the LCS of P1 and q1 and we'll append it there before X and that's going to be our longest common subsequence so that's expressed as LCS of p 0 and q0 is equal to 1 which comes from X Plus LCS of P1 and q1 the second case is when p 0 and q0 don't end with the same character so let's just call those characters X and Y and again there are some preceding characters before X and Y let's call them P1 and q1 again they could be any lengths and what we do in this case is we'll say okay let's just get rid of one of the characters let's just say x and we will find the LCS of P1 and q0 which is what I wrote here and we'll do the same thing with Y and find the LCS of P0 and q1 and we'll take the longer one of those so that's expressed as LCS of P0 q0 is equal to maximum or the larger one of those here's a recursive solution in code we Define the function LCS of PQ n m and n and M those are integers they are here because I don't want to uh recreate strings every time I call this function here's what I mean so let's say p equals ABC and we have Nal 2 then instead of looking at the whole string we'll just look at the first two characters and it's the same thing with q and M if Q is ABC and M is one we'll just look at the first character so this way we don't have to reproduce strings every time and here's our base case if n equals z or m equals 0 that means we're looking at an empty string so we'll just return zero and I'm storing uh this result in the result variable and returning it here if that's not the case and if the first Char if the last character of p and the last character of Q are the same we'll just return 1 plus LCS of PQ nus one M minus one and if that's not the case the last characters are not going to be the same but I wrote this just for clarity and what we're going to do here is take LCS of PQ n minus one m and LCS of PQ n m minus one and we'll take the maximum one of those and return that here's a quick analysis over a recursive solution we'll look at one of the worst case scenarios when p and Q don't have any characters in common and we'll look at this particular example when P equals AA and Q equals BBB first we'll call LCS of PQ 23 because we have two characters and three characters and to find that we need to call LCS of PQ 13 I just abbreviated as l13 and we'll also need to call l22 and to find l13 we need to call l03 which is a base case and l12 and so on that's what this diagram shows and as you can see the problem with this approach is that there are a lot of duplicates in our computation so we are Computing l12 twice the exact same competition and we're Computing l11 three times and that's why this is very wasteful and it's very slow in fact the time it takes to find the or original LCS is about an order of 2 to the power of n plus m in the worst case scenario and dynamic program says why not just store all those intermediate results so we can make this uh function run faster so now that we found a recursive solution we're going to memorize or store the intermediate results to make our function run faster here's a memorized version of our previous recursive function the only things that changed from the previous function are these three lines and what we're doing here is we're storing the intermediate results in this array in this two dimensional array of height n and width M and every time this function is called we ask ourselves do we or do we already uh have this result so we're initializing each element to undefined and we ask ourselves do we already have have it and if we already have the intermediate results if this is not undefined or if it's already defined then return that instead of going through the whole function and if that's not the case we go through the whole function find the result but before we return it we store it in this array so what's the run time for this one thing you can see right here is that we reach this last line only at most n m times because that's the number of variable combinations we have the possible variable combinations we have and so we go through this whole function only at most n m times and in this part we call LCS at most twice so the number of recursive calls is at most to NM times and each time the time it takes to execute each call is a constant time so the whole time complexity is an order of n * m which is much better than what we had before so we found a recursive solution and we memorized intermediate results and now we can come up with the bottom up solution which is an optional step in our recursive and memorize Solutions what we did was let's just say for this particular example P equal a a and qals aab what we did was we called LCS of PQ 23 and we said okay to find this we need to call LCS of PQ 13 and LCS of PQ 22 and so on so we started at the top and we went down so it's a top down approach we can also use a bottom up approach so start with m equal Z and Nal Z and ask ourselves what's LCS of PQ z0 that's that's of course zero and these are going to be all zeros and we can fill out this whole table so what's LCS of pq11 for that one we'll be comparing just these two characters so that's going to be one in the code we are actually using this the information from here and same thing with Nal 1 m equals 2 we're comparing these three characters so that's going to be one that comes from this part so we're going to fill out this whole table that way once we fill out this whole table we can just look at the last value Nal 2 and m = 3 and that's the value we wanted in the first place all right hopefully you like the video if anything was unclear please let me know and if you like this one you might also like this other video I have about dynamic programming with Fibonacci Sequence and if you want to watch more videos like this one you can just subscribe right here and thanks so much