Name: 最長公共子序列(動態編程) (Longest Common Subsequence (Dynamic Programming))
Uploaded: 2021-01-14T10:21:13.000Z
Duration: 10 min 13 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

形容詞最高級

Hey, guys, this is my dynamic programming tutorial with the longest common sub sequence problem as our example.

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

祈使句型

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.

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

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.

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.

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.

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

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.

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

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

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.

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.

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.

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.

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.

22 And so So we started at the top and we went down.

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.

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.