Intro to Dynamic Programming 2

I continuation of my first lecture on dynamic programming: https://tobyho.com/video/Intro-to-Dynamic-Programming.html. In this one we explore the longest common subsequence problem, a classic example in dynamic programming.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : this is a continuation on the talk on
00:05 : dynamic programming so last time we
00:08 : we went over the fibonacci sequence
00:10 : problem and we showed how you can
00:14 : use a table
00:15 : to cache the results that you've already
00:18 : computed
00:19 : and then you can
00:20 : use those intermediate results
00:23 : to um
00:24 : as this sub
00:26 : um sub
00:28 : problem solutions
00:30 : that will be useful for the larger
00:32 : problems
00:34 : um and that that speeds up things
00:36 : by a lot uh actually
00:39 : i
00:40 : last time i i didn't show you how
00:43 : dramatic a speed up it can be so i will
00:47 : do that now
00:49 : [Music]
00:50 : so if we do
00:53 : run this
00:54 : fibonacci program
00:56 : um there it returned with the value
00:59 : pretty quickly
01:00 : but we're only doing
01:03 : well okay
01:05 : actually let me
01:06 : show the slow version first because this
01:08 : is the fast version
01:10 : so i'll comment out the part where it
01:12 : looks up that table
01:14 : and and inserts into that table so this
01:16 : should be the slow version now
01:20 : duh except for that one second
01:23 : oh let me do this
01:25 : so so the table only has the entries for
01:28 : one and two so it's going to look up the
01:30 : table for those
01:31 : so that
01:33 : so that it it at least stops
01:35 : uh there's at least a terminating
01:37 : condition to the recursion
01:39 : okay so if you do this for a large
01:42 : ish number
01:44 : it's actually going to take a while
01:47 : for the program
01:50 : to finish
01:52 : yes
01:54 : i don't know if i want to wait that long
01:56 : let me do a smaller number
02:01 : let's do 50.
02:11 : well okay i don't know if i want to keep
02:14 : waiting but as you can see it takes a
02:16 : while
02:17 : just to calculate the 50th fibonacci
02:20 : number uh if we on the other hand turned
02:24 : on the cash
02:25 : feature
02:27 : then we get the result instantaneously
02:30 : and that's how big a difference it can
02:33 : make
02:34 : and the reason it's taking so long
02:36 : again
02:37 : as we we saw last time
02:40 : um is
02:41 : we're doing a lot of redundant
02:42 : calculations that were already done
02:44 : before so the caching
02:47 : makes this speed up possible um
02:52 : one thing um i also
02:55 : sort of hand waved last time a little
02:57 : bit but gonna make make it explicit this
02:59 : time
03:00 : is um
03:02 : alternatively you could do the bottom up
03:05 : approach for every given dynamic program
03:08 : programming problem
03:10 : you can do it the recursive way with
03:12 : caching but you can also do the bottom
03:14 : up way
03:16 : most of them you can um and for the
03:19 : fibonacci problem you would you would
03:21 : just make a table um
03:25 : that's the size or make an array i
03:27 : should say that's the size of
03:30 : the uh
03:33 : like like if you're getting the nth
03:35 : number in the sequence then you would
03:37 : make a array of size n
03:39 : and you just fill up each number in the
03:42 : sequence
03:43 : and uh
03:45 : starting from the bottom so if i run
03:48 : this program
03:53 : uh you'll see how it works so that
03:54 : actually calculates every
03:56 : number inside the sequence and put it in
03:59 : puts it in an array basically and then
04:02 : the result is just the last item in the
04:04 : array
04:06 : and
04:08 : so today's problem we're going to deal
04:10 : with
04:12 : is
04:13 : the longest common subsequence and uh
04:17 : this
04:18 : um
04:20 : this is an interesting problem and it's
04:23 : it's harder than the first one than the
04:26 : fibonacci or the coin problem that we
04:28 : looked at
04:29 : uh because
04:31 : uh we're gonna if we do it this bottom
04:34 : up way with with like uh with like an
04:37 : array we're gonna end up with a two
04:39 : dimensional array and i'll show you what
04:41 : that looks like
04:43 : um
04:44 : so let me explain this problem first
04:48 : so this is the longest common
04:50 : subsequence problem it's a classic
04:53 : problem
04:54 : for for teaching the dynamic programming
04:56 : concept
04:58 : and
04:59 : the
05:00 : uh
05:01 : there's this concept of subsequence
05:04 : let me explain that first
05:06 : so
05:07 : the example given is
05:09 : ace is a subsequence of abcde
05:13 : and the reason a's is a subsequence of
05:16 : abcde is because
05:20 : you can get two a's from abcde by
05:24 : deleting characters
05:26 : from abcde so i can delete b
05:30 : and i can delete e
05:33 : and the result is ace
05:36 : thus
05:37 : ace is a subsequence of abcde
05:41 : um another way of saying that is
05:43 : um
05:44 : [Music]
05:45 : the string a's
05:47 : is a uh
05:49 : is a string where each each character
05:53 : uh belongs in the second string
05:56 : abcde and each
05:59 : and sort of the each character
06:02 : is like an increasing order of the order
06:05 : that is within
06:07 : uh the second string so the a the c in
06:10 : the first string has to come after a
06:14 : uh in the second string and the e in the
06:17 : first string has to come
06:19 : after c in the second string
06:22 : okay
06:24 : so that's what a subsequence is
06:26 : and uh the this problem is like given
06:29 : two strings
06:31 : uh i want you to
06:32 : return the length
06:35 : of their longest
06:37 : common subsequence
06:42 : what does that mean
06:45 : well in this case ace is a perfect like
06:48 : it's just a subsequence
06:50 : of abcde but what if
06:53 : the first string had some letters that
06:56 : are not in the second string like
06:58 : i don't know
07:01 : uh
07:04 : i'll add a b
07:07 : uh
07:09 : so i'll add a b a b is actually in here
07:13 : so that's
07:14 : interesting uh i'll add something else
07:17 : i'll add y
07:23 : so
07:24 : if i had two strings like this
07:27 : i'll add another letter maybe m here
07:31 : that then the the longest common sub
07:34 : sequence between them is still ace
07:37 : uh trimming off this guy
07:40 : and uh trimming off these two guys
07:43 : uh does that make sense so far
07:46 : yeah any questions okay
07:49 : um
07:50 : so how would we do this um
07:55 : any
07:56 : intuitions anybody wanna throw at me
08:04 : um
08:05 : well
08:06 : yes
08:08 : i mean
08:09 : this is thinking stream of consciousness
08:11 : more than anything yeah but we know that
08:14 : if it's a subsequence that we have to
08:16 : find a
08:17 : first and then we look to see if there's
08:19 : the second part of the sequence i think
08:21 : so for example we know that a b c d
08:24 : e is
08:27 : longer right so we probably want to
08:30 : first check for a
08:32 : and then see if there's an ac like now
08:34 : that i can realize why this is going to
08:36 : take forever so it's probably not the
08:38 : right solution you look for a but below
08:41 : then keep going in the sequence until we
08:43 : hit a c and if we don't hit a c then we
08:46 : can start with the next uh letter in the
08:49 : first sequence you know and then just
08:51 : find the longest version starting with
08:54 : each letter
08:56 : um does that make sense
08:58 : longer i'll like start
09:00 : like oh you're saying like try to
09:04 : let me figure out where the longest one
09:06 : is so if we have if we're starting with
09:08 : a we're looking for a in the second
09:10 : sequence you're kind of
09:12 : i think
09:14 : you're kind of saying you're
09:16 : i think what you might be
09:18 : leading us to is like do like try to
09:21 : match a c e
09:23 : maybe
09:25 : um
09:26 : here
09:29 : no
09:30 : try oh if you see yes look for an a
09:33 : first like like you're like or look for
09:37 : you have an ace
09:39 : so and you have a position
09:41 : at
09:42 : the a of ace
09:44 : uh so you're gonna look for the first a
09:47 : and then if you look for the first a if
09:49 : you found the a which we did here
09:52 : then you're gonna advance this pointer
09:54 : to c right
09:56 : right
09:57 : and then you're gonna start
09:59 : at
10:00 : the letter after
10:02 : this guy's a hsb
10:05 : you start in here and you're going to
10:06 : look for ce right
10:08 : or you're looking to look for c right
10:10 : you're going to look for the first c
10:12 : after that
10:13 : and then you're you're going to find it
10:15 : here and i have another match so and and
10:18 : all the while you're accumulating how
10:19 : many letters
10:21 : you've gotten so at first it was one and
10:24 : then you got two
10:26 : and then um
10:28 : and then now that you found c you're
10:30 : gonna up the pointer here
10:34 : and then you're gonna again look for
10:36 : starting at d you're gonna look for the
10:38 : e you're gonna find it here and then
10:40 : you're gonna say hey i found three
10:43 : exactly i mean there's other like things
10:45 : you can do to return early because
10:46 : obviously if it's the length of the
10:48 : sequence like there's things but i don't
10:50 : think that really matters for big o
10:52 : notation
10:53 : um
10:55 : but then like let's say that these were
10:57 : bigger ones and you might have to go
10:59 : through again and say like hey were
11:01 : there any c's before i got to the first
11:03 : pointer uh and if there were
11:06 : theoretically there could be a longer
11:07 : sequence before you know you get to your
11:10 : first pointer yes
11:12 : so you're saying this algorithm may not
11:14 : necessarily yield the optimal so like
11:17 : the longest one
11:19 : well i assume that you're going to tell
11:20 : me what the optimal solution i mean it's
11:22 : going to yield the longest one because
11:24 : if we start from the beginning so if
11:26 : we're doing ace we found what the
11:28 : longest
11:30 : substring is starting with a so then i
11:32 : want to move on to say c
11:35 : and really i only have to start before
11:39 : the a sequence because everything else
11:42 : is going to do it so like let's say that
11:44 : there were letters before the a
11:46 : i could actually stop once i hit a and
11:49 : then you know add
11:51 : the
11:52 : rest theoretically because um
11:56 : well i have to think about that but the
11:58 : point is i can go through each letter
12:00 : and see if there is a longer subsequence
12:03 : based off of where my pointer is on the
12:05 : first one
12:06 : um
12:07 : yeah
12:08 : um
12:09 : hold on hold on i think you have a point
12:11 : there but i'm not totally catching it so
12:14 : you're saying
12:15 : so like pretend before the a in the
12:18 : longer substring there is like
12:21 : c e
12:22 : yeah so let's pretend it's c-e-a-b-c-d-e
12:26 : and then we're looking for ace
12:28 : you know theoretically
12:30 : i found that ace is already a sub-string
12:32 : but let's pretend i don't just return
12:34 : because i know that that's the longest
12:35 : possible substrate
12:38 : c
12:39 : so now i would be like okay well what's
12:41 : the longest substring if i start with c
12:44 : and so the longest substring if i start
12:45 : with c is going to be two
12:48 : um even though it happened there
12:50 : yeah yeah uh what what what if it was
12:55 : c e a b
12:58 : b
12:59 : and then you went for ace
13:02 : right so then i would see that and then
13:04 : and then you would if you found a
13:07 : then that skips the ce and then we lost
13:10 : these two letters here then i would have
13:12 : to check starting from the c
13:15 : to see like okay what is the longest
13:17 : substring starting with c and that would
13:19 : be c e which is 2.
13:21 : so so
13:23 : yes yeah that's a good point yeah and
13:25 : that's sort of the the
13:27 : case that we're trying to suss out like
13:30 : um if if you
13:33 : it's not good enough to just look for a
13:36 : because that could have skipped some
13:38 : valuable letters
13:40 : so
13:41 : um
13:41 : [Music]
13:43 : so we we want to start
13:45 : at this maybe what should like start
13:48 : from the a
13:50 : for the first glow and then start from
13:52 : the c on the second go and start from
13:54 : the e
13:55 : in the third go etc
13:57 : that's what that's what you're saying
14:01 : stream of um
14:02 : yes
14:04 : that's actually very good uh and that's
14:06 : that's uh that's a there's a valid
14:09 : solution
14:10 : um
14:11 : but it's not the fastest solution
14:14 : um and that your solution actually works
14:17 : uh but it's gonna have a big o of
14:20 : uh
14:22 : n
14:22 : squared
14:24 : i believe
14:25 : or
14:26 : where n where n is the length of
14:30 : times m i believe where m is
14:34 : that string and n is
14:36 : that string
14:37 : because you're you're
14:39 : like you're going through this string
14:41 : essentially twice
14:44 : or half of twice
14:48 : it's a triangle kind of thing
14:50 : um
14:52 : so
14:53 : so that's a good intuition um
14:56 : but the way we can do better than that
14:59 : is um we say
15:03 : hey we just we're gonna scan
15:05 : from
15:06 : the left to the right
15:09 : uh character by character
15:18 : i just put like another letter here
15:22 : is that a word um so
15:26 : so
15:26 : we're gonna well let's do a simple case
15:29 : first go back to the simple case first
15:31 : so
15:34 : we're gonna have a pointer
15:37 : that's keeping track of where we're
15:38 : looking uh on on each string and then
15:42 : we're gonna compare the character at the
15:45 : pointers
15:46 : and if it matches
15:48 : then we can actually safely
15:51 : move the pointer over for for both of
15:53 : them
15:55 : we can just simply like hey the a
15:58 : matches we can
16:00 : plus one
16:01 : on our longest common subsequence length
16:05 : that we have so far
16:07 : and then we can break it into a sub
16:09 : problem where
16:11 : we're doing the same thing to the
16:13 : substrings
16:15 : i see
16:17 : and that always works because even if
16:19 : there was another a later that doesn't
16:22 : take that doesn't add to the total score
16:25 : like we we could if another a like here
16:28 : comes comes up
16:30 : and yeah we lost the opportunity to
16:32 : match this a with that a but it doesn't
16:35 : subtract from our score we still get one
16:37 : even if you match this a versus this a
16:40 : it doesn't matter right
16:42 : so we put a c
16:45 : i mean i i don't know what order you
16:46 : want to do this but if we did like c a b
16:48 : c d e like how how we would account for
16:52 : you know
16:53 : yeah let's do that case now
17:03 : okay so the question is like if if the
17:06 : letters under the cursor are not the
17:08 : same
17:09 : then what do we do
17:11 : um
17:12 : well
17:12 : we we can't
17:14 : sort of advance both of the pointers uh
17:18 : or we don't want to
17:20 : um like last time because well we
17:23 : actually can't it would be incorrect
17:26 : because that is advancing the pointer
17:28 : kind of means you've found a
17:31 : match for it and we so we don't want to
17:34 : advance but we we want to shift over one
17:37 : of them like if we shift over this one
17:40 : then we will find the match
17:42 : on the next turn
17:44 : um the problem is
17:48 : what if it
17:49 : what if uh
17:51 : that skips over something useful because
17:54 : maybe
17:55 : maybe it's c a b c e d versus
18:00 : uh
18:01 : a
18:02 : c hey
18:04 : i don't know like like there's something
18:06 : useful here and we're matching we're
18:09 : comparing these
18:11 : and if we advance this one then we will
18:14 : miss out on the opportunity to match
18:17 : this c over here
18:20 : whereas in this scenario
18:22 : it's good to skip this one so in this so
18:26 : in the top scenario
18:28 : the desired uh
18:31 : step
18:32 : is to skip over the top string whereas
18:35 : for the bottom one
18:36 : the better
18:37 : the better solution is to skip this the
18:40 : bottom string does that make sense
18:45 : because if we skip over this a on the
18:48 : bottom that we get to match this cap
18:52 : [Music]
18:53 : yeah so that i think that's the question
18:55 : so how do we do that without
18:57 : you know iterating uh over again and
18:59 : getting to the oh
19:01 : and
19:02 : let's go
19:04 : yeah so what we want to do is
19:07 : we're gonna try both possibilities we're
19:10 : gonna try both
19:12 : uh
19:13 : advancing the pointer in string one
19:17 : and we're also gonna try advancing the
19:19 : pointer in string two
19:21 : as well
19:22 : uh
19:23 : so in in the other words
19:25 : um if if we if we have like a situation
19:28 : where we have a letter and we can't see
19:31 : what letters are coming after
19:33 : the current letter
19:35 : the nature of the algorithm
19:38 : and if the letters are not matching
19:40 : what we're going to do is we're going to
19:42 : try
19:43 : matching the rest of the letters in
19:45 : string 1
19:48 : with
19:50 : the string dirt this the current state
19:52 : of the string two as this
19:54 : and we're also gonna try matching
19:57 : the current state of string one as it is
20:00 : with the rest of the letters in string
20:02 : two
20:04 : and then we're gonna try uh
20:06 : the algorithm on that
20:08 : and that
20:09 : recursively and we're gonna see which
20:12 : one does better
20:13 : and we're gonna pick the one that's
20:15 : better that returns the longer sequence
20:26 : still there
20:27 : yeah
20:28 : okay um
20:31 : i don't know if i explained that nicely
20:34 : but uh
20:36 : let's try this let's try this
20:38 : i'm actually gonna
20:41 : okay
20:43 : i'm gonna call this longest
20:46 : [Music]
20:50 : okay so
20:52 : so basically we're gonna
20:53 : i'll call this lcs
20:55 : uh so we're gonna do abcde
20:59 : versus
21:02 : is
21:04 : and it's it's just gonna print a number
21:07 : that's how it's gonna do
21:09 : yeah and in this case the number should
21:11 : be uh three
21:12 : because it's ace
21:14 : uh what's another example
21:17 : we said something like
21:21 : lazy or something
21:24 : and that should also be
21:26 : ace
21:27 : um another example we talked about was
21:30 : like
21:33 : what if there's
21:35 : a c in front
21:39 : uh
21:40 : then we should also get ace i'll just
21:42 : start with this
21:43 : and we'll come up with counter examples
21:52 : i have s1 and s2
21:56 : um
21:56 : okay so
21:59 : let's check for
22:01 : um let's check for the
22:03 : length first so if
22:08 : if the length is
22:11 : zero for either of them
22:20 : then we'll just return zero
22:24 : so now we start this other algorithm
22:26 : where we have this cursor
22:29 : um
22:30 : and the cursor is just
22:32 : pointing we're just going to use a
22:34 : substring to trim off peel off letters
22:37 : from each string when we when we call
22:40 : the
22:41 : recursively called the function again so
22:44 : here we're just going to look at the
22:45 : first letter because the first letter
22:47 : effectively is the cursor
22:51 : or maybe we want to
22:54 : or maybe we want to do it with the
22:56 : cursor like i and j
22:59 : like that
23:01 : which one do you prefer do you prefer
23:03 : have like an index cursor
23:05 : or just imply that
23:07 : the beginning of the string
23:09 : the first character is the cursor and
23:11 : we'll just trim away at the string
23:14 : um
23:15 : yeah we can just trim away the string
23:17 : that's fine
23:18 : okay
23:20 : okay so in that case we're gonna say
23:23 : hey if
23:25 : the first letter
23:27 : is the same
23:29 : in both of the strings are the same
23:32 : um we're gonna trim away
23:34 : one letter from both of them
23:37 : uh so the answer
23:39 : is going to be we got one because this
23:42 : this match counts for one
23:45 : and then we recursively call ourselves
23:48 : with uh in in python the way to trim
23:50 : away a letter like a substring in
23:52 : javascript it would be substring
23:55 : one
23:56 : like that
23:57 : but in python it's
23:59 : there's a slicing operator
24:02 : that looks like one colon
24:05 : so that's how we trim away the first
24:07 : string
24:12 : what's that
24:15 : [Music]
24:23 : okay
24:25 : um all right
24:26 : so now uh so that's the case one that
24:30 : else
24:31 : else what we want to do as i said is um
24:34 : we want to try two cases one the case
24:37 : one is we want to trim away one letter
24:39 : from the first string but keep the
24:42 : second string intact and then vice versa
24:45 : and we want the best of those
24:48 : so
24:49 : uh answer one maybe
24:54 : but we but we're not going to add one
24:56 : because we don't have a new match so we
24:59 : can't
25:00 : add one to to the the length of the
25:02 : longest common sub subsequence in this
25:05 : case so
25:06 : case one or answer one is
25:09 : we trim away one letter from the first
25:11 : string but we keep the second string
25:14 : intact
25:16 : and then case two is
25:19 : we keep the first string intact
25:21 : but trim away a letter for the second
25:23 : string
25:28 : and
25:29 : we're going to take the max of that
25:31 : whichever one is the better one
25:35 : go say
25:36 : that's the one and that's the answer
25:39 : we'll return the answer
25:43 : let's see how this works
25:51 : three three and three
25:53 : i guess that's right um
25:58 : uh
25:59 : oh one thing
26:01 : let's just do one of them i'm gonna use
26:03 : my debugger to
26:05 : help us visualize what's happening
26:10 : okay i think i say can say c calls
26:23 : okay
26:24 : let's see this
26:26 : like this okay
26:28 : so
26:29 : so what happened
26:30 : let's see who can piece back together
26:32 : what happened
26:34 : so uh so initially we called the lcs
26:37 : function on these two strings
26:41 : the result was three but that was based
26:44 : on these sub-calculations over here
26:50 : because in order to calculate the answer
26:54 : for these guys we we have to calculate
26:57 : the answer for these guys so
27:01 : in this case we trimmed off the a from
27:03 : both of them
27:04 : so we're comparing bcde to ce
27:10 : um
27:11 : as a sub calculation
27:16 : [Music]
27:17 : okay and then in order to get and in
27:20 : order to calculate the
27:21 : uh the number for these two substrings
27:25 : we actually have to try two cases
27:28 : uh this case
27:31 : and this case it's like
27:33 : the first case trimming off this b
27:37 : and then the second case trimming off
27:39 : this e here i mean this c here
27:44 : um
27:46 : and
27:47 : let's follow just one of these paths
27:49 : down so so and and then we go further
27:52 : down and then because this now the this
27:55 : c
27:56 : here
27:57 : actually matched this c
27:59 : and for that reason we got another point
28:02 : again another count in the length count
28:05 : and then we can trim off the c and so
28:07 : we're comparing the d e versus the d
28:10 : and then
28:12 : and then we have two cases to compare uh
28:15 : the case of
28:16 : taking away the d
28:18 : which gets us e versus e
28:21 : and that eventually gets us another
28:23 : point so this point gets added to
28:26 : this point gets added to this point we
28:28 : get three um
28:31 : that is how the algorithm works
28:34 : does that make sense
28:36 : hopefully
28:38 : yeah i think so yeah i
28:41 : have that like yeah it's a little
28:43 : complex but um that's what it's doing
28:46 : but um in this case also
28:48 : since we're doing dynamic programming
28:50 : um
28:53 : we might be doing some redundant work
28:55 : let me see yeah like this is redundant
28:58 : work for we're comparing the two e's
29:01 : here
29:02 : um
29:03 : [Music]
29:07 : we're comparing d e and e
29:10 : in in two separate cases here so there's
29:13 : definitely some redundant work and
29:16 : because of that
29:18 : refactor that though can we throw this
29:20 : into elite code and just make sure it
29:22 : passes all the test cases
29:25 : oh
29:27 : uh
29:28 : it won't
29:29 : because this is gonna be extremely slow
29:32 : for multiple reasons but let's do it
29:40 : uh i'll just
29:58 : i think it'll pass the first case
30:00 : probably
30:02 : there it passed the first case
30:04 : and then if i try to submit through all
30:07 : the cases
30:08 : it's gonna exceed the time limit i'm
30:10 : pretty sure
30:12 : yeah said so
30:16 : um
30:18 : and uh and then that's because
30:22 : uh if we can see what the fourth test
30:25 : gate or one of the test cases is with
30:27 : the time
30:28 : limit exceeded
30:30 : so it's not even that long
30:32 : yeah this this one is not even that long
30:34 : but uh i mean i could
30:36 : i think we could um
30:39 : or we could put that
30:42 : um
30:43 : you know i'm worried about one that says
30:44 : wrong answer so like the time limit
30:46 : exceeded makes sense for a refactoring
30:48 : but can we check in on also the wrong
30:50 : answer
30:51 : it's not a wrong answer it is the time
30:53 : limit exceeded on this input
30:56 : like while it was performing this input
31:00 : because because it says time limit
31:02 : exceeded so it was already oh my god
31:05 : that's embarrassing that it was already
31:08 : exceeded the time limit on a very very
31:11 : small input
31:13 : um
31:14 : so let me try running that locally
31:25 : oh wow it does take a long time i wonder
31:28 : why um
31:32 : like um
31:35 : yeah
31:37 : okay
31:39 : i'm gonna
31:40 : do the
31:41 : the call stack thing on it
31:44 : and oh even that is ticking too long
31:49 : okay um
31:51 : so
31:52 : there's probably something about this
31:54 : string that has a lot so that's there's
31:57 : a time when
31:59 : you you should think to yourself maybe
32:01 : some caching would be uh helpful here
32:05 : um so so again we're gonna apply the the
32:08 : dynamic programming principle of when
32:10 : there's a lot of redundant computation
32:12 : going on we're gonna cache things
32:14 : um
32:16 : so so can i actually
32:19 : go back to it
32:21 : back to
32:22 : here
32:23 : yeah the
32:25 : actual thing so like i see the ones that
32:27 : say time limit exceeded but then there's
32:29 : the one at the bottom that says wrong
32:31 : answer you're saying
32:33 : oh sorry this is i this is other
32:35 : submissions that i've done in the past
32:39 : oh okay
32:40 : yeah
32:41 : like you can see the test cases
32:43 : yeah the only one we've done in this
32:45 : session is this one
32:47 : got it okay sorry yeah that's a
32:51 : yesterday
32:52 : um
32:53 : so
32:57 : so let's do
32:58 : a
32:59 : make a table and then we're gonna
33:02 : like
33:03 : we're gonna jam the strings together
33:06 : into a unique key into the table
33:09 : and now when we get an answer we'll
33:11 : stick in the table and we'll look it up
33:13 : if there's a match
33:15 : okay so so
33:16 : um in order to do this though
33:18 : i want a
33:20 : one
33:21 : new table instance
33:24 : to be created for each call
33:38 : hello
33:41 : i think you might have cut out for a
33:43 : second there
33:44 : yeah
33:45 : for a moment okay
33:48 : i hope i'm back okay so i'm gonna
33:50 : continue so i'm adding this table
33:53 : parameter
33:54 : i have to make sure i remember to pass
33:56 : it to all the recursive costs to myself
34:00 : and now i'm going to do the same thing
34:02 : that i basically did for the fibonacci
34:05 : example which is
34:07 : i'm gonna look up the table
34:09 : um maybe not for
34:11 : maybe right after this
34:13 : this check here i'm gonna look up the
34:15 : table by the key i'm gonna
34:17 : compute the key
34:19 : which is just
34:21 : you know string one
34:22 : plus
34:24 : a separator
34:26 : plus string two that's the key
34:28 : although i have to mention this is not
34:30 : the this is probably still going to be
34:32 : too slow
34:35 : but for a different reason
34:38 : so i'm going to say if the key is in the
34:41 : table if we have an entry in the table
34:43 : by that key
34:44 : we're just returning
34:46 : the cache value
34:48 : and down here if we we've gone on and
34:52 : calculated the answer
34:54 : i'm gonna enter it into the table
34:59 : okay
35:01 : let's try this
35:06 : and now it actually returns in
35:08 : in a fast manner
35:10 : uh okay let's try this in
35:17 : and delete code see if we will accept
35:20 : our answer
35:26 : uh oh i forgot to pass in a table
35:34 : okay so that works for this example
35:37 : if i try to submit it
35:40 : it's probably still gonna time out
35:43 : yeah it still times out
35:46 : uh for
35:49 : oh
35:51 : it won't show me this
35:54 : there
35:55 : it still times out for extremely long
35:57 : example
36:00 : and
36:01 : the reason the times out this time is
36:03 : because
36:06 : each time we create a substring
36:10 : it makes a copy of a really really long
36:12 : substring
36:14 : so the more times we do that the more
36:16 : memory we consume on the system
36:19 : and because it's a really long string to
36:21 : begin with we're ending up
36:23 : creating like many many copies of
36:26 : uh very long strings still
36:29 : so
36:31 : uh a better way to do this
36:33 : or a way to do this that actually passes
36:36 : the time limit that finishes before the
36:38 : time limit is actually to do what uh
36:42 : do it with the indexes and instead of
36:45 : trim away at the strings we do it with
36:47 : the indexes so let's go ahead and do
36:49 : that
36:50 : um
36:51 : so we have to adapt these to
36:54 : the index so we're never going to trim
36:56 : away at these strings anymore first of
36:58 : all so we're already we're going to pass
37:00 : in string one and string two
37:10 : and then for the first
37:14 : thing
37:15 : during the strings and then the
37:17 : and then the indexes i thought the
37:20 : function
37:21 : strings
37:22 : yep exactly so
37:24 : whereas before we had we pass in two
37:27 : strings now we're gonna pass in two
37:28 : indexes and then two strings and the
37:32 : strings we're never gonna change them
37:36 : so we're gonna have to modify these guys
37:38 : here so if we want to trim away one
37:41 : character of a string uh what we're in
37:44 : fact saying is we want to move the
37:46 : cursor
37:47 : by one so what we want to do is here i
37:50 : i'm gonna
37:52 : take the next version of i i want it to
37:54 : be i plus one and the same with j i want
37:56 : it to be j plus one
37:58 : and and also
38:01 : you know we wanna when we call this like
38:03 : later on when we go back here we call
38:06 : this we're gonna want to pass in 0 and 0
38:08 : for the indexes
38:10 : and also the length check we have to
38:13 : convert it to a index check now so index
38:17 : would be like if
38:18 : index is
38:20 : greater or equal to
38:23 : the length of the string
38:25 : basically
38:27 : then we're at the end of the string
38:33 : and and then we're going to return 0.
38:35 : and then
38:37 : here
38:39 : instead of looking up index 0 we would
38:41 : look at lookup index i and index j and
38:46 : then again here we're gonna do i plus
38:48 : one here no change means we just pass j
38:53 : uh over
38:54 : without change and here we pass i over
38:57 : without change
38:59 : and then also
39:01 : instead of using the strings as the keys
39:05 : this was probably a thing that was
39:07 : killing us over here
39:09 : like we're going to concatenate these
39:10 : two extremely long strings
39:13 : into this extremely long key and use
39:15 : that in the table
39:17 : now we're just going to use the indexes
39:19 : as the key
39:21 : and um
39:22 : in python you can actually do
39:25 : do this which is called a tuple this is
39:28 : a tuple of two numbers
39:30 : and you can actually use that as a key
39:32 : into a tape oh this would be i and j
39:36 : and you can use that in the as an index
39:39 : into the table
39:41 : and uh
39:43 : let's let's attempt this
39:58 : okay the first one works
40:01 : let's see if it passes all of the
40:04 : okay it does pass all of them
40:06 : um
40:08 : okay
40:09 : do any any questions at this point so
40:12 : this
40:13 : this is uh similar to our uh
40:18 : our fibonacci solution where we use the
40:20 : table
40:21 : basically um
40:24 : but we had more cases to consider in
40:26 : this problem
40:28 : okay uh i do want to go over
40:30 : the bottom up approach as well
40:33 : um
40:35 : this actually gets kind of interesting
40:38 : so
40:42 : the bottom up approach for this example
40:45 : can actually be visualized as a
40:47 : two-dimensional table
40:50 : um and
40:52 : [Music]
40:54 : so
40:55 : let's say we
40:57 : our string was what was our string
41:02 : okay
41:13 : um what we're going to do is
41:15 : so this is a grid
41:25 : so we're gonna actually use a cell in
41:28 : the grid to represent
41:31 : what's the longest common subsequence
41:36 : of
41:37 : between
41:38 : the string
41:40 : starting at this position versus
41:43 : starting
41:45 : at this position so it so does the
41:48 : number in this cell should be
41:51 : what's the longest common subsequence
41:53 : between e and e
41:55 : and the answer to that is one because
41:58 : e matches e
42:02 : and then in this cell
42:04 : uh
42:05 : we're asking what's the longest common
42:07 : sub subsequence between d e
42:11 : and e
42:12 : and the answer to that is
42:14 : one okay and then these are all going to
42:18 : be one
42:19 : because
42:21 : i know that because none of these match
42:23 : e
42:24 : oh it doesn't even matter if they match
42:26 : e or not actually we already matched the
42:28 : e so that's gone
42:30 : um
42:31 : you can't match more than one e if you
42:33 : only have one e on the other side so and
42:37 : then these are gonna be one
42:41 : okay
42:42 : um
42:43 : now we're gonna fill in this square this
42:45 : square is hey what's the longest common
42:48 : subsequence between d e
42:51 : and c e
42:53 : and the answer to that again is one
42:56 : but the way we know it's one the the the
42:59 : calculation we do to get one is
43:02 : we actually look at this value and look
43:06 : at this value and we get the larger of
43:08 : the two um
43:12 : because
43:15 : because um
43:17 : like if if
43:19 : if earlier on we got more scores
43:22 : up until this point then that's the
43:25 : that's the one we should pick um
43:28 : so here though is still one
43:31 : um but here
43:33 : the c's are matching so we get another
43:36 : score
43:37 : so
43:38 : and when when you get a match what you
43:40 : do is you you add one but what do you
43:43 : add one two you add one to the one
43:45 : that's diagonal from you
43:48 : and that's that one
43:49 : because you're gonna consume
43:51 : a letter
43:52 : and then after you consume this letter c
43:57 : because here you're matching between c d
43:59 : e
44:01 : and c e
44:02 : and after you consume this c on both
44:05 : sides you're going to end up with d e
44:08 : versus e so you want the answer for
44:11 : d e versus e and that's this guy
44:18 : so what we want to fill in here is 1
44:20 : plus this one which is two
44:24 : and here we're going to have two because
44:26 : we want the max between this guy and
44:28 : this guy so we have two
44:32 : and here again we have two
44:35 : and here
44:37 : d and a don't match so we want the max
44:39 : between this and this
44:41 : and that's one
44:44 : uh this is the max between this and this
44:46 : and that's actually two
44:51 : and here we want the max between here
44:54 : and here and that's both of them are 2.
44:57 : so this is 2
44:59 : and this a matches
45:01 : so
45:02 : we get one more point and we get one
45:04 : added to this guy
45:07 : that's three any questions
45:11 : okay so this is what we're gonna
45:13 : this is the algorithm we're gonna write
45:16 : and it's actually equivalent to
45:19 : this algorithm that we wrote recursively
45:22 : um it's an equivalent algorithm
45:25 : um except we're gonna do it
45:27 : in the bottom up way and uh to make
45:30 : life a little bit easier for us we're
45:33 : gonna add
45:34 : an extra row
45:36 : and an extra column
45:38 : and fill in with zeros over here
45:41 : so that we don't have to do boundary
45:43 : checking
45:45 : i'm just doing this so that the code
45:46 : will be
45:47 : much simpler to write
45:50 : although you don't necessarily have to
45:51 : do that
45:53 : you can do boundary checking instead
45:56 : okay so
45:58 : let's
45:59 : do it
46:00 : um so i'm going to comment out the
46:02 : function we had
46:04 : write a new version of this function but
46:06 : this can be bottom up
46:09 : now maybe i leave this one
46:11 : and call this bottom up
46:23 : okay
46:27 : now i'll test this function
46:32 : okay so the first thing we're going to
46:33 : do is we want to make a table of the
46:36 : appropriate size
46:39 : um
46:42 : and um
46:45 : i think i'm gonna go for i in range of
46:50 : length of string one
46:53 : plus one
46:55 : plus one because we want that extra
46:58 : uh
46:58 : row
47:00 : uh for for those zeros
47:03 : and then uh and then i'm gonna
47:05 : append a row to the table
47:08 : for each character in string one plus
47:11 : one
47:12 : uh and we're going to say
47:15 : in python there's this shorthand
47:18 : for you you can multiply
47:20 : arrays
47:22 : to make a longer array so i can say
47:24 : an array with a zero in it multiply that
47:27 : five times
47:29 : and we'll get an array that has five
47:31 : zeros in it like that
47:33 : so i'm going to use this shorthand here
47:35 : to make an array of the appropriate
47:38 : length
47:39 : and the length we want is the length of
47:43 : s2 plus one
47:46 : okay so so we're going to end up with
47:48 : this table i'll print out the table
47:52 : let's run that
47:53 : to see it
47:58 : okay there's our table it's uh
48:03 : nested
48:05 : uh each
48:06 : each row has four letters that's the
48:08 : length of a's plus one
48:11 : and it's got six
48:13 : rows
48:14 : which the length that's the length of a
48:16 : b c d e plus one
48:19 : uh okay now we're gonna go in
48:21 : and
48:23 : we're gonna do
48:25 : uh
48:26 : two nested uh
48:28 : classical for loops except that python
48:31 : doesn't have classical for loops
48:34 : i'm gonna do it with a while loop the
48:37 : old school way
48:38 : [Music]
48:45 : and i'm gonna actually start at the
48:48 : end
48:50 : i'm going to
48:51 : start from the right side of the table
48:54 : so i'm going to count in reverse
48:56 : basically i'm going to do i
48:59 : and subtract 1 from i on each turn and
49:02 : i'm gonna do the same thing for j i'm
49:04 : gonna start at the bottom and then work
49:06 : my way up
49:20 : okay so those are our two nested loops
49:23 : and uh we're actually gonna do the exact
49:25 : same logic as we did over here
49:28 : which is that so if
49:32 : um
49:33 : if the
49:34 : letters at each cursor
49:39 : are the same
49:43 : then we're going to
49:45 : come up with
49:46 : uh
49:47 : we're going to
49:48 : take add one to the count
49:52 : uh
49:53 : and to which count to the
49:55 : to the cell that's directly diagonal to
49:58 : us
49:59 : which is going to be in
50:01 : so
50:03 : answer
50:04 : is one plus
50:06 : the answer that's diagonal from us
50:09 : which is going to be
50:10 : one
50:12 : i plus 1 and i plus j
50:16 : and
50:17 : and here is why i put in that extra
50:20 : column and row of zeros
50:23 : that way this will
50:25 : already have a value in it which is zero
50:28 : the first time i go through and do this
50:31 : so i
50:32 : if if i was like the
50:35 : bottom corner
50:36 : of the table like if initially i is
50:39 : going to be here
50:42 : and it's going to go diagonal and i put
50:45 : a 0 here so that it will be able to get
50:47 : it
50:50 : and then
50:51 : else
50:53 : if we did not have a match
50:55 : then what we're going to do oh oh we
50:57 : want to plug the answer into
51:00 : uh
51:04 : into the current location in the table
51:07 : so as it goes into here
51:09 : we're sticking the answer into the cache
51:14 : and then
51:15 : yeah otherwise
51:17 : we get our answer
51:19 : via
51:20 : the max of table
51:22 : i plus one
51:26 : uh we advance the i pointer
51:30 : in one case and then we advance the j
51:33 : pointer in the other case and then we
51:35 : pick the better of the the bigger of the
51:37 : two and that's our answer and now we're
51:39 : going to stick it into our table
51:45 : okay
51:47 : and
51:48 : at the end of all this
51:51 : let's see what the table looks like
51:57 : oh
52:01 : this should be plus one
52:08 : i plus one by j minus one
52:11 : yeah that should be j
52:14 : okay that's what our table looks like
52:17 : let me print the table a little bit
52:19 : better
52:25 : okay that's our table
52:28 : so
52:31 : if i read that correctly
52:35 : uh oh
52:37 : it's the same numbers as
52:39 : what we did by hand
52:41 : just flipped
52:43 : uh
52:47 : like this
52:49 : one one one
52:51 : like this three is yeah it's the exact
52:53 : same table i just just um
52:57 : rotate it
52:58 : um
52:59 : so we're getting the correct answer
53:02 : and the the final answer we want to
53:04 : return
53:05 : is just the number
53:07 : and the top left corner which is index 0
53:09 : 0.
53:22 : so three
53:24 : um
53:25 : all right let's
53:26 : any questions about this algorithm like
53:29 : does it
53:30 : intuitively make sense
53:33 : um i'm gonna plug this in see if it
53:36 : checks out
53:51 : okay that works i'm gonna submit it to
53:53 : all of them
53:57 : and it worked
53:59 : um
54:00 : it actually did better than the
54:02 : recursive one
54:04 : with caching
54:06 : in terms of both runtime and memory
54:08 : usage
54:11 : um
54:12 : [Music]
54:14 : why would that be
54:16 : uh
54:17 : that was gonna be my question
54:21 : um well it goes through
54:27 : i mean it's basically going to go
54:29 : through
54:30 : each
54:32 : you know it's
54:34 : the length of input a times the length
54:36 : of input b which is
54:39 : uh
54:41 : what is that in o notation is that n
54:44 : the a length of input a
54:47 : plus length of input b of n plus
54:54 : yeah so that's n and then for the other
54:57 : one it is
54:59 : going to be
55:02 : m
55:09 : which
55:10 : thing are you trying to describe like
55:12 : you're trying to say the people of
55:14 : something the big of what
55:16 : of each of these so they're different
55:18 : right like clearly the runtime and
55:19 : memory is very different in both of
55:21 : these solutions so i was trying to
55:23 : calculate well what is the thing
55:29 : as i as i understand it the big o should
55:32 : be identical for both of these algorithm
55:35 : so
55:37 : so the reason that the actual
55:40 : performance is different
55:42 : um
55:43 : i think is something else it's not that
55:46 : their
55:47 : sort of algorithmic complexity is
55:50 : different
55:51 : it's um
55:52 : [Music]
55:53 : it's more like um
55:55 : dependent on
55:57 : well depending on something that's
55:59 : happening the the way that python is
56:02 : performing the things
56:03 : um
56:05 : and my suspicion is i don't have a clear
56:09 : answer um
56:11 : like if if i dug into it like that
56:14 : looked into the performance of it i can
56:16 : probably get a clear answer but like i
56:19 : have a guess
56:20 : uh one guess is
56:23 : um
56:24 : the bottom up one does not call
56:27 : functions
56:28 : there's no function call in here it's
56:31 : just one function
56:33 : with a couple of nested loops
56:36 : and uh so it doesn't have the overhead
56:38 : of calling functions
56:40 : and calling functions actually
56:42 : has a
56:44 : like a
56:47 : like a can be significant overhead if
56:49 : you do it a lot
56:51 : which you are
56:52 : when you're doing a lot of recursive
56:54 : calls so because every time you call a
56:56 : function
56:58 : there's a stack you have to remember
57:01 : uh first of all you have the local
57:04 : variables like you're calling this
57:05 : function
57:07 : i'll just
57:09 : the the language has to remember you're
57:11 : inside of this function call and then if
57:13 : this function call calls another
57:15 : function or or not another function
57:18 : calls itself
57:19 : but with different parameters
57:21 : it has to remember that so that when
57:23 : this function exits it comes back to
57:26 : this function with with the state of
57:28 : this one intact still
57:30 : so every time you make a function called
57:32 : this stack grows taller
57:37 : memory
57:38 : yeah and yeah and it takes memory this
57:40 : is using memory to to do all these
57:43 : things and then and each each
57:45 : frame inside the stack has to remember
57:48 : some local variables
57:50 : in there like like in in our case it was
57:53 : like well these are the local variables
57:57 : uh this is a local variable and this is
57:59 : a local variable so each frame has these
58:02 : things to remember within it
58:04 : and then so
58:05 : so this can grow tall and then come back
58:08 : down again grow tall come back down
58:10 : again
58:10 : etc although because we have this
58:13 : caching it doesn't go too crazy i don't
58:16 : think but it'll probably go really tall
58:18 : and then come all the way back down
58:20 : probably go do something like that
58:22 : whereas comparing it like here
58:25 : there's always just one eye and one j at
58:28 : a time so it's not going to be consuming
58:31 : tons of memory in order to
58:34 : uh you know the way that we're moving
58:36 : those pointers is that it's really kind
58:38 : of replacing in memory those things so
58:40 : you'll never be stacking
58:42 : you know as you did in that diagram and
58:44 : then
58:45 : um
58:47 : the other thing is so that and then as
58:49 : far as run time
58:51 : i guess you know just not having
58:54 : i guess this is just a more efficient
58:55 : way of running python um i mean the
58:57 : memory part is easier to visualize and
58:59 : then the runtime i think is a little
59:01 : harder without knowing the real ins and
59:03 : outs but it's not like one is taking
59:05 : forever and the other one isn't you know
59:08 : so
59:09 : well the the the calling of the function
59:12 : has implications for the runtime as well
59:14 : it takes time to set that stuff up and
59:16 : then tear that stuff down
59:18 : right
59:19 : um
59:22 : yeah okay yeah we're at time so i won't
59:25 : dwell on it
59:27 : longer so uh i'll close it here unless
59:30 : you have a last question unless someone
59:32 : has a last question
59:35 : okay well thanks everyone for your
59:37 : attention