# Intro to Dynamic Programming 2

Published on Oct 27th 2021Duration: 59:39Watch on YouTube

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: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: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: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: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: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: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: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: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: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