Now let me explain what the longest comments of cigarettes Problem is, we have two strings.

Let's call it P and tube.

And we're trying to find a common string.

And we're trying to find the longest one, of course.

And in this case, that would be be a on one thing to note here is that these characters are not necessarily contiguous.

We're gonna solve this problem using dynamic programming.

But let's first talk about this general procedure that we have 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 members the intermediate results or restore the intermediate results to make you run faster.

And finally, we can come up with something called a bottom up approach on.

I'm gonna explain what it means later.

This is an optional step.

By the way, here's a recursive solution.

We're gonna write dysfunction LCS longest coming Sep sequence off Pisa on Q zero.

The two inputs tricks on.

We're gonna return the length of the longest comments of sequence instead of with a sub sequence itself.

So with our previous example, we're gonna return instead of B a.

D.

We're gonna return the length of it, which is three.

The idea behind any Riker Shin is that, of course, we're gonna take down this problem into smaller problems, and we're gonna sell those instead on their two kisses.

We need to consider for that the first cases when p zero and Q zero and with the same character.

Let's call it Let's just call the ex on there.

Some proceeding characters.

Let's call them P one and two on.

They could be any lengths.

They could be empty or not empty.

What we say in this case is that the longest comments of sequence of Pisa and Q zero must end with X, and so we'll get rid of these and we'll find the LCS of P one on cue on on will upend it there before X.

And that's gonna be our longest coming sub sequence.

So that's expressed as LCs of P zero and Q zero is equal to one, which comes from X plus LCs of P one on cue.

One the sick on cases when P zero and Q zero don't end with the same character.

So let's just call those characters X and Y on again.

There are some preceding captors before X and Y is called them P Juan and Cue one again.

They could be any lengths.

And what we do in this case, he's will say, OK, let's just get rid of one of the characters.

Let's just say X on.

We'll find the LCS of Q p one and Q zero, which is what I wrote here.

And we'll do the same thing with why on find the LCS of P zero and Q one and we'll take the longer one of those.

So that's expressed as else's appease accuse oh is equal to maximum or the larger one of those.

Here's a recursive solution.

In code, we define the function LCs of peak U.

N.

M.

On and an M.

Those are intruders.

They're here because I don't wanna recreate strings every time I call this function.

Here's what I mean.

So let's say Peco's ABC on we have any goes to then, instead of looking at the whole string, will just look at the 1st 2 captors, and it's the same thing with Q and M.

If Que ese ABC and Amy's one.

Well, just look at the first capture.

So this way we don't have to reproduce drinks every time.

And here's our base case, if any, co zero r M e co.

Zero that means we're looking at on empty string, so we'll just return zero on I'm storing this result in the result viable on returning it here.

It doesn't in the case on if the first, if the last character of P and the last character Q are the same will just return one plus LCS of P Q and minus one and minus one.

And if that's not the case, the last characters are not gonna be the same.

But I wrote this just for clarity on what we're gonna do Here is take Elsie S O.

P.

Q and minus one em on Elsie's of Peak, you and M minus one, and we'll take the maximum one of those on return that here's a quick analysis over a recursive solution.

Well, look at one of the worst case now Iris, when P and Q don't have any characters in common Well, look at this particular example.

When P goes a a and Curie Coast BBB first, we'll call L C s A p cute to three because we have two characters on three characters.

And to find that we need to call L.

C s off Peak you 13 I just I be rated as l 13 We'll also need to call l 22 on to Final 13 We need to call l 03 which is abase case and I want to.

And so that's what this diagram shows on.

As you can see, the problem with this approach is that there are a lot of duplicates in our competition.

So we're computing l one too, twice the exact same condition.

We're computing l 113 times, and that's why this is a very wasteful and it's very slow.

In fact, the time it takes to find the orginal LCS is a bottle in order to to depart of and plus M in the worst case scenario and dynamic program says why not just store all those intermediate results so we can make this function run faster?

So now that we found a recursive solution.

We're gonna memorize or store the intermediate results to make our function around faster.

Here's a memory's version over previous recursive function.

The only things that changed from the previous function are these three lines on.

What we're doing here is we're storing the intermediate results in this array in this two dimensional ray of height and on with em on every time dysfunction is called, we ask ourselves, Do we or do we already have this result?

So we're initializing each element to undefined, and we ask ourselves, Do we already have it 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 hole function on.

If that's another case, we go through the whole function, find a result.

But before we return it with, store it in this ray.

So what's the runtime for this?

One thing you can see right here is that we reach this last line on Lee most and M times because that's the number off viable combinations.

We have the possible viable combinations we have.

And so we go through this whole function on Lee upmost and M times.

And in this part we call l CS at most twice.

So the number of recursive caused is a most to N m times on each time.

The time it takes to execute each call is a constant time.

So the whole time complexity is on order off end times m, which is much better than what we had before.

So we found a recursive solution on we memorized intermediate results.

And now we can come up with the bottom absolution, which is an optional step in our recursive and memories solutions.

What we did was, let's just say for this particular example pee goes, Aye, aye And Cuco Xabi.

What we did was we called L C s off P Q 23 and we said, OK, to find this, we need to call L.

C s off P Q 13 on LCS of P Q.

22 And so 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 EMI ko zero on Eneko stare Oh, and ask ourselves what's L C s f p cute 00 that's that's That's of course, zero.

And these are gonna be all zeros.

Uh, we can throughout this whole table.

So what's LCS off?

Peak?

You won one for that one will be comparing just these two characters, so that's gonna be one in the code.

We're actually using these day information from here on.

Same thing with any goes one Emmy goes to We're comparing these three characters.

That's gonna be one that comes from this part.

So we're gonna fill out this whole table that way.

Once we fill out this whole table, we can just look at the last value and it cost you and Emma goes three on.

That's the value we wanted in the first place, or I Hopefully you like that video.

If anything was unclear, please let me know on if you like this one.

You might also like this other video have about dynamic pro Ming with Fibonacci sequence on.

If you want a multiple videos like this one, you can just subscribe right here.