I give a lecture to the Insiten crew introducing them to dynamic programming. The time-traveling debugger was employed here to demonstrate the performance characteristics of inefficient recursive algorithms.

The following transcript was automatically generated by an algorithm.

- 00:01 : uh one thing about dynamic programming
- 00:03 : is uh
- 00:05 : the whole
- 00:07 : like the name
- 00:08 : is
- 00:09 : completely
- 00:11 : meaningless
- 00:13 : uh
- 00:14 : and
- 00:14 : and also doesn't tell you anything about
- 00:16 : what it actually is
- 00:18 : um
- 00:19 : and so so this is just
- 00:21 : uh just don't get too bothered by the
- 00:24 : name it it doesn't really reflect what
- 00:26 : it is uh
- 00:28 : i think the easiest way for me assuming
- 00:32 : you have had some experience with
- 00:34 : recursion
- 00:36 : uh
- 00:37 : the the best way to describe it is
- 00:40 : uh
- 00:41 : it's recursion
- 00:43 : with caching
- 00:45 : um
- 00:46 : and i'll use a recursion with
- 00:49 : memoization some some people like
- 00:51 : recursion
- 00:54 : with caching or
- 00:56 : memoization
- 00:58 : if you want to use a fancy term like
- 01:00 : that
- 01:01 : um
- 01:02 : and
- 01:04 : a good way to
- 01:05 : show that i'm going to be using python
- 01:08 : um
- 01:09 : for for the code examples and
- 01:12 : the reason is because i want to use some
- 01:15 : features of my debugger which i think
- 01:18 : will help in illustrating
- 01:20 : some of the points
- 01:23 : so
- 01:24 : let's let's run this
- 01:30 : program
- 01:32 : and we get the answer 55
- 01:36 : okay so
- 01:40 : uh okay uh
- 01:43 : there's a this is a very quick refresher
- 01:45 : on the fibonacci in case you didn't know
- 01:47 : so fibonacci is a
- 01:49 : sequence of numbers in which
- 01:52 : the nth element so this is the first
- 01:57 : this is the first one one second one
- 01:59 : third one fourth one fifth one
- 02:02 : oops no no no fifth six the nth element
- 02:06 : is the sum of the previous two elements
- 02:09 : so
- 02:10 : so
- 02:11 : the first two elements are both one
- 02:14 : and then the third is the sum of one and
- 02:16 : one and the fourth one is the sum of one
- 02:18 : and two etc that's how you build up the
- 02:21 : sequence
- 02:22 : and this is a recursive solution that
- 02:25 : does that uh you to to get
- 02:28 : the number the number
- 02:30 : at
- 02:31 : location n
- 02:33 : whatever n might be assuming n is
- 02:35 : greater than one
- 02:37 : if it's
- 02:38 : two or below you return one
- 02:41 : um
- 02:42 : if it's greater than that i'm going to
- 02:45 : get the
- 02:47 : the previous the numbers at the previous
- 02:49 : two locations by recursively calling
- 02:52 : myself to calculate them okay uh now
- 02:56 : this works
- 02:58 : uh but is it's a very uh inefficient
- 03:01 : algorithm
- 03:02 : to do this even though this is a very
- 03:04 : very
- 03:05 : like classic example
- 03:07 : for teaching recursion
- 03:09 : um this is actually extremely
- 03:11 : inefficient now does anyone have
- 03:15 : a clue as to why this is inefficient
- 03:23 : anyone it's like super nested recursion
- 03:25 : so
- 03:27 : like
- 03:29 : my instinct is there some sort of like
- 03:32 : direct formula where you can go from n
- 03:36 : straight to
- 03:37 : you know
- 03:38 : value that i don't know about
- 03:40 : that that is true there that it that
- 03:43 : does exist
- 03:44 : uh but but we're not going to talk about
- 03:46 : that there's actually a big o of one
- 03:48 : algorithm for calculating the fibonacci
- 03:50 : number
- 03:51 : but uh let's not talk about that let's
- 03:53 : pretend that doesn't exist or um we're
- 03:56 : going to talk about this
- 03:58 : algorithm and but i want to
- 04:01 : sort of illustrate why this is extremely
- 04:04 : inefficient
- 04:05 : um
- 04:06 : so
- 04:08 : um
- 04:09 : one of the features of my time traveling
- 04:11 : debugger is that you can this is utility
- 04:15 : called see uh not seeker see calls
- 04:20 : that can allow you to um
- 04:23 : that can allow you to see all of the
- 04:26 : function calls that happened
- 04:29 : in in nested
- 04:31 : way
- 04:32 : okay so this is actually what happened
- 04:34 : in order to calculate 55 at the end
- 04:40 : so i'll just
- 04:43 : read through
- 04:44 : parts of it to lead you through what's
- 04:46 : actually happening uh in order to
- 04:48 : calculate fit
- 04:50 : of
- 04:51 : with n equal to 10
- 04:53 : we're gonna have to ask what's the
- 04:55 : result of fib with n equal to 9
- 04:58 : and what's the result of fib with n
- 05:01 : equal to 8
- 05:02 : which is actually
- 05:05 : all the way down here
- 05:08 : um uh so so so this guy is like hey can
- 05:12 : you calculate
- 05:14 : n equal to 9 for me and n equal to 8 for
- 05:17 : me
- 05:18 : but in order to calculate n equal to 9
- 05:22 : n equal to 9 has to know the result of n
- 05:24 : equal to a
- 05:26 : and then n equal to 8 has to know the
- 05:28 : result of n equal to 7
- 05:30 : etc etc
- 05:31 : until we get all the way down here and
- 05:33 : then it's like oh it's obvious the
- 05:35 : result is 1.
- 05:37 : um
- 05:38 : and
- 05:41 : well i mean the first thing you probably
- 05:43 : thought when i showed you this is like
- 05:45 : this is a lot of stuff
- 05:48 : right
- 05:49 : why is it a lot of stuff and is this
- 05:52 : stuff necessary
- 05:54 : and um
- 05:56 : you can actually very clearly see that
- 05:59 : it's not necessary because
- 06:02 : you can see a lot of duplication of
- 06:05 : stuff being calculated recalculated
- 06:08 : one example is
- 06:12 : here
- 06:14 : this fragment here
- 06:19 : appears again
- 06:21 : over here
- 06:24 : uh not only that
- 06:26 : this fragment here
- 06:29 : it actually occurred here
- 06:33 : and here
- 06:35 : and later on here
- 06:39 : um
- 06:41 : so so it's just not it's not just that
- 06:43 : there's recursion going on but a lot of
- 06:46 : unnecessary
- 06:48 : unnecessary calculation
- 06:51 : because the same thing is getting
- 06:54 : calculated multiple times uh like
- 06:56 : like
- 06:57 : and
- 06:58 : n equals four is getting calculated here
- 07:02 : and here and here and later on
- 07:06 : here as well
- 07:07 : you know
- 07:08 : but
- 07:09 : but at the top level
- 07:11 : at the top level like well
- 07:14 : n equals 9 calculate
- 07:16 : n equals 8
- 07:17 : but n equals 8
- 07:20 : is asked for again
- 07:23 : so
- 07:24 : so anyway the point is
- 07:26 : um
- 07:27 : there's a lot of redundancy of work
- 07:30 : and uh that can easily be eliminated via
- 07:34 : caching
- 07:35 : so so let's do caching
- 07:37 : right so we're doing we're still doing
- 07:39 : recursion but we're just going to add in
- 07:41 : caching
- 07:42 : and
- 07:44 : the way i'm going to add in caching is
- 07:46 : just by saying hey i'm going to make a
- 07:50 : dictionary
- 07:51 : uh each key value pairs is the
- 07:54 : the key is the input and the
- 07:56 : value is the output now i'll even put in
- 07:59 : the first two values which is
- 08:02 : the first element should give you one
- 08:04 : and the second element should give you
- 08:05 : one
- 08:06 : if and if i did that i don't even need
- 08:08 : this if statement anymore
- 08:10 : i just say
- 08:11 : is n in the table
- 08:13 : if it is just return your cash value
- 08:17 : um
- 08:19 : oh i i should return it
- 08:22 : um and
- 08:26 : and once we get the answer i'm going to
- 08:28 : stick it into my table
- 08:30 : so that it can be reused next time that
- 08:33 : same number is act asked for
- 08:36 : so i'm going to put the key is the input
- 08:39 : which came from here
- 08:41 : and then the value is the answer and
- 08:43 : then at the end i still want to return
- 08:45 : the answer so
- 08:48 : so we've added caching aka memorization
- 08:52 : to this recursive algorithm
- 08:55 : by just changing a couple of bits here
- 08:59 : and if we run this again we get the same
- 09:01 : answer but now
- 09:04 : we get this graph which is much
- 09:07 : smaller
- 09:09 : which means the computer had to do much
- 09:11 : less work
- 09:13 : um
- 09:15 : so
- 09:17 : yeah so that's that's a recursion with
- 09:20 : caching um
- 09:24 : and i fully get that just gives you an
- 09:26 : intuition of what dynamic programming
- 09:29 : is
- 09:34 : when you read the literature on dynamic
- 09:36 : programming there's a
- 09:38 : what they typically say is
- 09:41 : there are two conditions
- 09:47 : for dynamic programming like two
- 09:49 : conditions sorry two conditions under
- 09:52 : which
- 09:53 : you
- 09:54 : if these two conditions held
- 09:57 : then you know
- 09:58 : a dynamic programming solution
- 10:01 : is a good one and those two conditions
- 10:03 : one is they call it
- 10:05 : uh optimal
- 10:07 : uh
- 10:09 : substructure
- 10:12 : optimal substructure what a word um
- 10:16 : did i spell this right yeah okay and the
- 10:18 : second one is uh overlapping
- 10:21 : sub problems
- 10:26 : and i'll just briefly explain what these
- 10:29 : means uh optimal substructure all that
- 10:32 : means is that
- 10:34 : the
- 10:35 : optimal
- 10:37 : solution or in some cases
- 10:39 : the optimal solution just means
- 10:43 : uh the correct answer
- 10:48 : or correct answer
- 10:50 : um
- 10:51 : when they say optimal solution
- 10:54 : they say it because a lot of times
- 10:56 : dynamic programming is used in
- 10:59 : in
- 11:01 : problems where you're trying to find the
- 11:03 : ops absolute best
- 11:05 : solution out of many possible solutions
- 11:08 : that's why they use the term optimal
- 11:10 : solution in the case of fibonacci
- 11:12 : sequence there's only one correct answer
- 11:14 : there's not many answers to choose from
- 11:17 : and then you have to pick the best one
- 11:19 : there's just one answer
- 11:21 : in any case
- 11:23 : what optimal substructure means is that
- 11:27 : the optimal solution or the correct
- 11:29 : answer
- 11:30 : depends on
- 11:32 : sub
- 11:33 : uh up depends on
- 11:38 : optimal
- 11:40 : solutions
- 11:44 : of sub problems
- 11:48 : uh so so
- 11:50 : so
- 11:51 : if you have the optimal solution or
- 11:53 : correct answer of your sub problems
- 11:56 : then you can use those answers to derive
- 12:00 : the your optimal solution
- 12:02 : of your parent problem and more or less
- 12:07 : what that means at the end of the day is
- 12:10 : you can use a recursive
- 12:12 : solution
- 12:13 : to to solve the problem
- 12:18 : uh what does overlapping sub problems
- 12:20 : mean um overlapping sub problem is
- 12:23 : actually exactly what you saw
- 12:26 : when when i did this
- 12:28 : without caching
- 12:32 : i'll do it again
- 12:35 : um
- 12:36 : this is a this is a very concrete
- 12:38 : display of overlapping sub problems
- 12:41 : because
- 12:42 : um
- 12:44 : the same
- 12:45 : sub problems are
- 12:47 : needed
- 12:48 : by multiple parent problems
- 12:50 : uh so the concrete cases are
- 12:53 : well the the
- 12:56 : fib of n equals eight
- 12:58 : is a sub problem
- 13:00 : that is needed by
- 13:02 : n equals nine
- 13:04 : but n equals 8 is also a sub problem
- 13:09 : over here
- 13:11 : that's needed by the
- 13:14 : original
- 13:15 : parent which is
- 13:17 : 5 of 10. flip of 10 needs flip of 8
- 13:22 : and flip up 9 but but because fib of 9
- 13:25 : also needs
- 13:26 : also needs to flip over 8.
- 13:28 : overlapping that this this guy
- 13:33 : yeah overlaps with
- 13:36 : with that and because of this
- 13:38 : overlapping uh if you don't do caching
- 13:41 : you're gonna get a lot of
- 13:43 : redundant and unnecessary calculations
- 13:45 : like we're seeing here and the caching
- 13:48 : just eliminates that
- 13:50 : okay any answers uh sorry any questions
- 13:53 : at this point
- 13:56 : or comment
- 13:58 : okay
- 14:00 : um
- 14:02 : okay the next thing
- 14:04 : to say is
- 14:06 : um
- 14:08 : whenever you have a dynamic programming
- 14:12 : uh
- 14:13 : solution
- 14:15 : you can
- 14:16 : either
- 14:17 : build these
- 14:19 : you can build the solution in two
- 14:21 : different ways
- 14:23 : um
- 14:26 : you can always convert between these two
- 14:28 : ways so two ways
- 14:31 : to
- 14:34 : solve dp
- 14:37 : and the first way is what you already
- 14:39 : saw which is recursion
- 14:42 : with caching
- 14:45 : uh the second way is called bottom up
- 14:48 : and the way bottom up works
- 14:51 : is
- 14:52 : your
- 14:53 : instead of
- 14:56 : and bottom up doesn't even require
- 14:58 : recursion i'll show you in a bit how
- 15:00 : that works
- 15:01 : um
- 15:03 : because you know that
- 15:07 : sort of uh
- 15:10 : you know with prior knowledge the order
- 15:12 : in which
- 15:13 : you're gonna need the
- 15:16 : the the solutions of the sub problem
- 15:19 : instead of starting at the top at n
- 15:22 : equals 10 and go downwards in this tree
- 15:26 : what you can do is actually go in
- 15:28 : reverse direction start at the bottom
- 15:31 : with n equal one
- 15:33 : and just say hey i already have the
- 15:35 : answer to n equal one and n equal two
- 15:38 : now let me calculate n equal three and n
- 15:41 : equal four and those are easy so when
- 15:44 : you get
- 15:46 : and when you get asked hey what is the
- 15:48 : tenth number in the fibonacci sequence
- 15:51 : all you're gonna do
- 15:53 : is
- 15:54 : you're gonna allocate an array
- 15:58 : and use this box here
- 16:00 : you're gonna allocate an array
- 16:04 : of ten numbers
- 16:13 : okay is that ten yeah
- 16:15 : and then you already know the first
- 16:17 : two are going to be one
- 16:20 : and then you're just gonna do
- 16:22 : oh
- 16:23 : and fill this in and add the previous
- 16:25 : two numbers together
- 16:32 : what's the next one
- 16:37 : and then you're done and and there's no
- 16:39 : recursion involved all you do is write a
- 16:41 : little loop
- 16:42 : to do this
- 16:44 : and then you can you know you subtract
- 16:46 : one and subtract two from the current
- 16:48 : index etc it's very straightforward
- 16:54 : but not not all problems
- 16:57 : will end up with a one-dimensional array
- 17:00 : some problems may end up with
- 17:03 : a matrix
- 17:05 : you know that's n by m
- 17:08 : um
- 17:09 : there's there might even be three
- 17:10 : dimensional ones depending on the
- 17:12 : problem
- 17:14 : um but but a simple problem like
- 17:16 : fibonacci you just end up with a one
- 17:19 : dimensional array you filled up fill
- 17:21 : that up and then you just return the
- 17:22 : last value from the array and you're
- 17:24 : done
- 17:28 : okay
- 17:29 : um
- 17:29 : [Music]
- 17:31 : so that's dp with the fibonacci sequence
- 17:34 : so let's do a different problem
- 17:36 : um
- 17:40 : okay
- 17:42 : um there's a problem
- 17:46 : called the
- 17:48 : is it the coin change problem i believe
- 17:51 : let me see
- 17:53 : i think on um
- 17:57 : on lead code
- 17:59 : there's a coin change problem yeah
- 18:14 : okay so this is the coin change problem
- 18:17 : and
- 18:19 : it's basically saying you're given a
- 18:22 : dollar amount
- 18:24 : um
- 18:26 : and
- 18:27 : let's say i don't know
- 18:28 : you have to make change for
- 18:30 : 475.
- 18:33 : how are you going to make change for
- 18:34 : that you have
- 18:36 : these denominations um the denominations
- 18:39 : are given
- 18:41 : to you as an array of numbers
- 18:43 : um
- 18:45 : maybe instead of like using decimals we
- 18:48 : could just do it in terms of cents or
- 18:50 : something
- 18:51 : so that we don't have to worry about
- 18:52 : decimals and then
- 18:54 : and then so in in the standard
- 18:57 : uh us currency
- 18:59 : what we probably have is like
- 19:02 : 500
- 19:04 : 100 for one dollar
- 19:06 : uh
- 19:08 : 25
- 19:10 : 10
- 19:11 : 5 and 1.
- 19:14 : and and then
- 19:15 : you you are allowed unlimited supply of
- 19:19 : denominations of each type so you don't
- 19:21 : have to worry about running out of
- 19:23 : quarters and stuff like that
- 19:25 : you just
- 19:26 : assume there's a limited amount
- 19:29 : um
- 19:30 : the
- 19:31 : this particular problem asks what's the
- 19:33 : fewest number of coins
- 19:37 : or denominations
- 19:39 : that you need uh to to make up that
- 19:41 : amount
- 19:43 : um how do you make change for this so
- 19:46 : uh
- 19:48 : so can somebody answer this like how
- 19:50 : would you make change for this
- 19:59 : is what's the i what's ideal change like
- 20:01 : four ones and three quarters oh you're
- 20:03 : just trying to get the smallest amount
- 20:05 : right yeah the smallest
- 20:07 : number of either coins or bills uh that
- 20:11 : the smallest number of stuff that you
- 20:13 : have to hand back to the
- 20:15 : customer i guess
- 20:16 : two two dollar bills and three
- 20:19 : i'll do that other bills okay
- 20:22 : two dollar bills
- 20:24 : inserted um
- 20:26 : but but how did you do that what
- 20:28 : algorithm did you use
- 20:30 : to use my
- 20:32 : familiar
- 20:34 : uh familiarness with the american
- 20:35 : currency yeah
- 20:38 : but that's not a that's not a teachable
- 20:40 : thing you can't you can't just say just
- 20:43 : do it you can't
- 20:45 : if somebody doesn't know already know
- 20:47 : how to do it you can't tell them just do
- 20:49 : it so what what what uh what algorithm
- 20:53 : would you use to do this
- 20:56 : i would probably
- 20:58 : do like a while mod
- 21:00 : not equal zero type of deal
- 21:03 : assign the remainder to some variable
- 21:06 : and uh
- 21:07 : do that like
- 21:09 : um
- 21:10 : you know
- 21:11 : de-escalating from the highest
- 21:14 : denominations to the lowest
- 21:15 : denominations until they're the result
- 21:18 : is zero but the input is zero okay very
- 21:20 : good yeah that's that's how i would do
- 21:22 : it as well i start subtracting
- 21:25 : starting from the highest denomination
- 21:28 : um
- 21:31 : well this is not gonna work for the five
- 21:33 : dollar bill
- 21:34 : so i move on to the two dollar bill
- 21:37 : which is going to work twice
- 21:39 : so i will have two times 200
- 21:42 : which will get us down to um
- 21:45 : 75
- 21:47 : and then we'll we'll try the 100 not
- 21:50 : going to work and then we're going to go
- 21:51 : to the 25
- 21:53 : and we'll end up with three
- 21:56 : quarters
- 21:57 : uh
- 21:58 : and we'll end up at zero so at the end
- 22:01 : we have five
- 22:03 : uh five
- 22:05 : denominations to hand back to the
- 22:07 : customer
- 22:08 : um
- 22:09 : is that the best algorithm
- 22:21 : and i'll show you the code for that
- 22:23 : because i already wrote that up
- 22:32 : i i i gave it away by the name of my
- 22:36 : algorithm
- 22:38 : oops uh but is this the best algorithm
- 22:45 : let's see so
- 22:48 : the criteria that you gave before is
- 22:51 : um
- 22:55 : uh i want to use the actual terms that
- 22:57 : you use for the criteria but uh
- 23:00 : uh
- 23:03 : uh well i wanted fewest number of coins
- 23:12 : oh
- 23:13 : well
- 23:14 : right like the caching is like or
- 23:16 : dynamic programming
- 23:18 : um
- 23:20 : what what even makes us turn to dynamic
- 23:23 : is this a dynamic programming algorithm
- 23:26 : first of all
- 23:27 : no
- 23:27 : it's not it's it's not um
- 23:32 : it
- 23:33 : well
- 23:34 : i guess it could be expressed in a
- 23:35 : recursive kind of way but i'm not using
- 23:38 : any kind of table
- 23:40 : to cache any intermediate results i'm
- 23:42 : not doing that so this is this is um
- 23:45 : this is actually a greedy algorithm
- 23:48 : um
- 23:49 : as my the name of my file shows
- 23:52 : um
- 23:54 : and the reason it is greedy is because
- 23:57 : uh
- 23:59 : while at each stage
- 24:02 : i could have chosen from a number of
- 24:05 : different choices
- 24:07 : i do not do that instead i always
- 24:10 : make a educated guess and go with only
- 24:13 : that
- 24:14 : and only that choice based on the
- 24:16 : educated guess and the educated guess is
- 24:19 : i'm always going to
- 24:20 : go for the largest denomination
- 24:25 : at any given moment
- 24:26 : until that runs out until that the
- 24:29 : denomination doesn't work anymore i'm
- 24:31 : always choosing the largest whereas i
- 24:34 : could have chosen any of the
- 24:35 : denominations
- 24:37 : at any point in time
- 24:39 : in making the change like why didn't i
- 24:41 : just choose a penny at the beginning
- 24:44 : of making the change i didn't because i
- 24:47 : i kind of intuitively knew that that
- 24:50 : would end up i would end up with a lot
- 24:52 : of coins
- 24:53 : so so i i didn't do that
- 24:55 : um
- 24:56 : are there cases though in which
- 24:59 : this greedy strategy does not give you
- 25:02 : the best solution
- 25:06 : um well i'll tell you the answer the
- 25:08 : answer is in the in the uh
- 25:12 : in the denominations that we have in the
- 25:14 : u.s
- 25:16 : the the greedy strategy is always
- 25:18 : optimal
- 25:20 : so
- 25:21 : so in order for
- 25:23 : for you to get a
- 25:25 : situation that it is not optimal we have
- 25:28 : to go to
- 25:30 : maybe a different country
- 25:33 : so let's say we live in a country
- 25:36 : where the denominations are
- 25:38 : 5
- 25:40 : 4
- 25:41 : annual
- 25:42 : one
- 25:44 : and then we had to make change for eight
- 25:48 : um
- 25:49 : so now if you use
- 25:51 : the greedy strategy
- 25:53 : we would say hey i can take one of five
- 25:57 : leaves me with three
- 26:00 : and then to do three i'm gonna have to
- 26:02 : do uh three ones
- 26:07 : i'm gonna have to do three ones
- 26:11 : i'm going to end up with four four coins
- 26:15 : but there's a better there's a better
- 26:18 : solution for eight because
- 26:20 : there's two times four
- 26:24 : uh so so well i would only end up with
- 26:27 : two coins so in in this fictitious
- 26:29 : country
- 26:30 : where their denominations are five four
- 26:33 : and one
- 26:34 : the greedy algorithm is not the optimal
- 26:37 : solution
- 26:40 : okay
- 26:41 : um
- 26:43 : now
- 26:44 : you know i i kind of have to
- 26:47 : sort of
- 26:49 : be creative to come up with a situation
- 26:51 : like this
- 26:52 : but you know
- 26:54 : use your imagination
- 26:56 : so things like this can exist uh it can
- 27:00 : exist in other domains as well although
- 27:02 : yeah making change is probably
- 27:05 : not the most pressing problem
- 27:09 : you know it's for an exercise
- 27:12 : um
- 27:13 : so now the question is
- 27:16 : now that we know that this greedy
- 27:19 : algorithm won't give us
- 27:22 : the best answer we're gonna
- 27:24 : need something different we're gonna
- 27:26 : need to
- 27:28 : not only try the largest denomination we
- 27:31 : actually potentially need to try all the
- 27:34 : different
- 27:35 : possibilities so like given 8
- 27:39 : we can
- 27:40 : and again the denominations are 5
- 27:44 : 4 and 1.
- 27:48 : we can
- 27:49 : structure this recursively uh step one
- 27:52 : i'm gonna choose
- 27:55 : five four
- 27:58 : i might just try all of the different
- 28:00 : options and see what i get if i choose
- 28:03 : five i end up with three
- 28:06 : if i
- 28:07 : try four
- 28:08 : then i end up with four
- 28:12 : and if i try one i end up with seven
- 28:16 : and
- 28:17 : this for three i i
- 28:19 : well
- 28:22 : four and five no longer work so i have
- 28:25 : to do like one
- 28:27 : to get two
- 28:29 : one to get one
- 28:32 : and then one again
- 28:34 : to get zero at the end
- 28:36 : and then he with four i could either do
- 28:40 : four
- 28:41 : and be done
- 28:43 : or i have to do one
- 28:45 : and get three
- 28:47 : and then i have to do
- 28:50 : one to get two
- 28:53 : one to get one
- 28:55 : and then
- 28:56 : one to get zero again and then when i'm
- 28:58 : at seven
- 29:00 : i have seven left
- 29:02 : there's more work to be done i'll let
- 29:04 : you imagine the rest because it gets
- 29:06 : slightly tedious over here um
- 29:09 : but the point is there's all these
- 29:10 : possibilities i might need to do
- 29:14 : one of the points i'll make is you can
- 29:16 : clearly see a overlapping subproblem
- 29:20 : which is this one
- 29:22 : versus this one
- 29:24 : i have i have
- 29:27 : uh i have two remaining
- 29:29 : uh and i need to make the change and
- 29:31 : give me the optimal change
- 29:33 : and that overlappings a problem will
- 29:35 : probably show up somewhere around here
- 29:37 : as well maybe multiple times and uh when
- 29:40 : that happens you know that's a good
- 29:42 : candidate for using dynamic programming
- 29:47 : so maybe
- 29:49 : we should
- 29:53 : we should try to implement that
- 30:02 : okay
- 30:05 : okay
- 30:06 : so let's do the recursion with caching
- 30:12 : um
- 30:14 : so
- 30:15 : let's do coin change
- 30:21 : i get the coins and the amount
- 30:26 : and the coins is just an array so i'll
- 30:29 : end up calling it probably like
- 30:32 : coin change
- 30:35 : five four and one
- 30:38 : and then the amount
- 30:39 : i used eight okay something like that
- 30:43 : and maybe i'll get the answer here
- 30:50 : and print it uh the answer should be two
- 30:53 : i guess the optimal
- 30:55 : choice is two of the four
- 30:59 : dollar coins or something
- 31:02 : um
- 31:03 : okay so how do we do this um we want to
- 31:06 : try
- 31:07 : all the possibilities so
- 31:10 : so uh
- 31:12 : for each coin
- 31:15 : that is a possible
- 31:16 : denomination i'm gonna try
- 31:20 : try taking
- 31:21 : taking a
- 31:23 : this coin
- 31:25 : and
- 31:27 : so if
- 31:28 : the amount of the coin is greater or
- 31:31 : equal to the current amount
- 31:34 : then i'm gonna take
- 31:36 : i'm gonna
- 31:37 : use this coin basically
- 31:40 : peel it
- 31:41 : from
- 31:42 : uh
- 31:44 : peel it from the amount um
- 31:47 : so
- 31:48 : so remaining
- 31:50 : um
- 31:52 : should i call this remix let's call this
- 31:54 : remaining although
- 31:56 : no i'm just gonna have it inside here
- 32:01 : okay
- 32:02 : so if i take this coin
- 32:05 : and i get this remaining value
- 32:08 : i'm gonna
- 32:10 : recursively call myself
- 32:13 : same coins but with the remaining
- 32:18 : amount
- 32:19 : uh that as a result of taking this coin
- 32:23 : and then this is the number of coins
- 32:29 : this is the number of coins from this
- 32:33 : this uh calculation of the sub problem
- 32:37 : um but
- 32:38 : because i took one coin here so my my
- 32:42 : num coins
- 32:45 : i should add one
- 32:50 : to mine
- 32:53 : does that make sense or maybe i could
- 32:54 : just do it inline like this
- 32:58 : so i
- 32:59 : so
- 33:00 : assuming this
- 33:02 : because this is recursion and because we
- 33:03 : have optimal substructure
- 33:06 : i'm gonna assume that
- 33:09 : the
- 33:10 : the result whatever this sub recursive
- 33:13 : call return is the optimal
- 33:17 : uh number of coins
- 33:19 : for for this particular sub problem so
- 33:21 : therefore
- 33:23 : um
- 33:24 : if i add one to it that's the solution
- 33:28 : for if i were to take this coin
- 33:31 : but i'm gonna try that for
- 33:34 : all of the possible denominations so out
- 33:37 : of all of these i'm gonna get this num
- 33:40 : coins and i want to get the best one
- 33:42 : um and
- 33:46 : a simple way to do that is just make
- 33:49 : make the best variable on the outside
- 33:54 : or i could just collect all of them and
- 33:56 : then just do a
- 33:58 : min
- 33:59 : on on all everything in the array or
- 34:02 : something but i could also just do have
- 34:04 : a best one on the outside and say
- 34:07 : maybe best is just
- 34:10 : yeah okay i'll just make best is nothing
- 34:13 : so if
- 34:14 : best is none
- 34:16 : or
- 34:18 : num coins is less than the current the
- 34:22 : best
- 34:23 : then best is the new num coins
- 34:26 : so
- 34:27 : if it hasn't been initialized yet then
- 34:30 : the best gets this num coins but if
- 34:33 : there is an existing best
- 34:36 : but my num coins is better than that i
- 34:39 : update the best
- 34:42 : makes sense
- 34:44 : and then i return the best
- 34:46 : uh
- 34:48 : at the end
- 34:52 : does that work
- 34:55 : it looks right
- 34:56 : it looks right okay i think so
- 35:00 : um is there
- 35:03 : sorry
- 35:04 : i was looking at something else for a
- 35:05 : second but are you handling the case
- 35:07 : where
- 35:09 : what if the amount minus coin is
- 35:13 : less than zero
- 35:16 : um
- 35:17 : oh queen experience never mind
- 35:20 : but but there but uh
- 35:22 : there is a case of
- 35:24 : else what happens
- 35:26 : um and i haven't really considered that
- 35:29 : so
- 35:31 : if
- 35:32 : well i i just wouldn't do anything
- 35:36 : i guess
- 35:37 : there could potentially be a case where
- 35:40 : none of the coins will work
- 35:42 : anymore
- 35:44 : um
- 35:45 : [Music]
- 35:46 : there could be a case yeah where you
- 35:48 : have another
- 35:51 : it could be it could just mean a bound
- 35:54 : is zero at that point
- 35:56 : but it potentially depending on your
- 35:59 : denominations like if your denomination
- 36:01 : doesn't have a one for example
- 36:03 : and your amount is one
- 36:06 : then there's no way to make the change
- 36:08 : so um
- 36:10 : and you probably want to have some way
- 36:13 : to indicate that that there's actually
- 36:15 : no way to make this change because we
- 36:18 : don't have a coin that's small enough
- 36:20 : for some reason in that country
- 36:22 : uh not likely because i imagine most
- 36:25 : countries have a penny
- 36:29 : as a nomination
- 36:32 : or something if you want right
- 36:34 : but uh but i think um
- 36:37 : we do have a problem and that wouldn't
- 36:39 : check for amount might be zero in which
- 36:42 : case none of the coins will make
- 36:46 : and what's that gonna happen
- 36:49 : i don't know
- 36:50 : let's see
- 37:00 : [Music]
- 37:06 : gotcha i'll just say best equals zero
- 37:08 : then because an amount of zero you don't
- 37:11 : need any points to make change for it
- 37:13 : it's not actually pretty safe if we're
- 37:15 : assuming that we can always make change
- 37:17 : for any
- 37:18 : real though the problem is zero is going
- 37:20 : to be less than anything
- 37:23 : so we're going to
- 37:27 : because
- 37:28 : here we're saying the best is the
- 37:30 : smallest and 0 is even smaller than that
- 37:36 : oh never mind it's reversed yeah i see
- 37:38 : yeah oh we could make this max hint or
- 37:41 : something but that would be
- 37:45 : yeah this is not that it's zero yeah
- 37:47 : yeah just do it like this
- 37:49 : um wait why are we getting
- 37:52 : none now
- 37:54 : i'm not sure let's debug
- 38:04 : okay
- 38:06 : um
- 38:10 : if coin is greater than the amount
- 38:15 : oh coin is five
- 38:18 : that's wrong isn't it oh it's less than
- 38:20 : or equal
- 38:22 : it should be less than equal
- 38:24 : okay
- 38:26 : um
- 38:36 : we're trying to add int and nun type uh
- 38:41 : we're returning the nun type
- 38:43 : presumably because uh
- 38:47 : none of these
- 38:48 : iterations hit probably
- 38:51 : with the debug
- 38:54 : okay so this is but we'll go back here
- 39:00 : it's probably because at some point
- 39:02 : you're gonna try to add one and null and
- 39:03 : it seems like python isn't cool with
- 39:05 : that
- 39:07 : right but but how do we get the null
- 39:09 : because the reason it would be no is
- 39:12 : because we return best and best we're
- 39:14 : still null right
- 39:19 : i'll go back to the point so that would
- 39:21 : be this point so if i go back we return
- 39:24 : we returned best which was none but how
- 39:27 : do we get that
- 39:28 : because at some point like five is not
- 39:30 : gonna work
- 39:32 : so the amount is actually zero
- 39:35 : we found
- 39:36 : so the amount in this iteration of the
- 39:40 : function the amount is zero so there's
- 39:43 : not going to be any coin
- 39:45 : i'm starting at zero but that was
- 39:47 : because somebody called it with zero
- 39:51 : uh in namely here the remaining was zero
- 39:56 : after
- 39:58 : after we
- 39:59 : we subtracted uh the coin one from the
- 40:02 : amount of one we ended up with
- 40:05 : remaining zero and now we're trying to
- 40:07 : make change for zero
- 40:10 : we didn't have anything to uh
- 40:12 : to handle the zero case amount equals
- 40:15 : zero so if amount equals zero we go
- 40:17 : through it we end up with best
- 40:20 : equals none and we return nothing that's
- 40:22 : not going to work
- 40:24 : um
- 40:25 : we could just if it's
- 40:27 : in the case of none we could just return
- 40:29 : zero at the end just add a little if
- 40:32 : statement here
- 40:33 : so we could do that
- 40:36 : then you handle the zero case too
- 40:40 : what
- 40:41 : oh
- 40:42 : oh you're saying just do it up here
- 40:46 : oh i mean no it doesn't matter to me
- 40:48 : but
- 40:49 : yeah that would be probably more elegant
- 40:51 : i suppose yeah i think this is more
- 40:53 : obvious when when people are reading
- 40:55 : this code this
- 40:56 : okay let's go this
- 40:58 : uh we get two which is correct whereas
- 41:02 : um
- 41:05 : we use the greedy one
- 41:23 : look at four
- 41:24 : yeah so this is
- 41:26 : uh this is the gives gives the more
- 41:28 : optimal answer
- 41:31 : um however
- 41:38 : oops
- 41:40 : however we get this situation where
- 41:44 : um
- 41:45 : let's see where the overlapping problems
- 41:49 : um
- 41:50 : we're asking for three here we're asking
- 41:52 : for three here again
- 41:54 : we're asking for three here again
- 41:57 : and we
- 41:58 : clearly asked for the same thing
- 42:00 : multiple times
- 42:02 : and that's inefficient where we're
- 42:06 : we're wasting cpu
- 42:08 : right
- 42:09 : so what we do is um we add a table
- 42:17 : no
- 42:18 : putting a global table is probably
- 42:22 : not good for this problem because
- 42:26 : in one in one instance you might get
- 42:28 : one denomination set in a different
- 42:31 : instance you might get a different
- 42:32 : denomination set
- 42:34 : so a global table
- 42:36 : doesn't really make sense so maybe you
- 42:38 : want to just pass in a table and you
- 42:40 : just initialize the table and pass it in
- 42:43 : here
- 42:45 : and i'll pass it through to the
- 42:47 : recursive calls
- 42:49 : and then here i'll do a lookup and say
- 42:51 : hey if
- 42:52 : the amount is already in the table
- 42:55 : return the table amount
- 43:00 : and
- 43:02 : when we do calculate the answer
- 43:07 : and this the best
- 43:09 : is the answer i will say
- 43:12 : put it into the table
- 43:23 : now we get
- 43:24 : much shorter execution
- 43:29 : uh makes sense
- 43:30 : um
- 43:32 : now
- 43:34 : just for fun
- 43:36 : any questions first
- 43:38 : before i go to the
- 43:40 : next thing
- 43:41 : uh like any maybe like
- 43:45 : any thoughts seeing this
- 43:48 : what what what are the things that occur
- 43:49 : to you when you when you're seeing this
- 43:52 : dynamic programming or maybe have you
- 43:55 : read about dynamic programming in the
- 43:57 : past
- 43:58 : and uh
- 44:00 : what were your thoughts about it
- 44:03 : seems like you can get pretty memory
- 44:05 : intensive so
- 44:06 : you probably want to make sure that it's
- 44:10 : yeah i guess worth worth that trade-off
- 44:13 : yes plus that you are paying for lookups
- 44:15 : constantly so
- 44:17 : it seems like you definitely have to
- 44:18 : cross a threshold for it to be worth it
- 44:22 : uh um yeah that that is true because
- 44:27 : uh uh
- 44:28 : if if i fill up a table with
- 44:31 : tons of data
- 44:32 : that's gonna take up memory uh this
- 44:35 : takes it away from other parts of your
- 44:37 : program that might need
- 44:39 : to use memory
- 44:40 : um
- 44:42 : one particular like
- 44:44 : real
- 44:45 : application real scenario where the
- 44:48 : memory might suffer is um
- 44:51 : that there is actually a
- 44:53 : parsing algorithm
- 44:55 : that is based on dynamic programming
- 44:58 : um and
- 44:59 : it's called the nearly the nearly um
- 45:02 : no not nearly the early the early
- 45:04 : pricing algorithm
- 45:06 : and it's based on the
- 45:09 : it's based on
- 45:10 : the dynamic programming in that it
- 45:12 : creates a table
- 45:14 : and it as it's parsing character by
- 45:16 : character it puts entries into that
- 45:19 : table
- 45:20 : for every character or every token
- 45:23 : that it encounters if you tokenize your
- 45:26 : characters your string first
- 45:28 : then it'll be per token um now what that
- 45:32 : means is the longer your input is
- 45:36 : the larger that table needs to be to
- 45:39 : hold up all of your tokens
- 45:43 : um
- 45:44 : and
- 45:48 : so how do you compare this like
- 45:51 : the dynamic programming version to the
- 45:54 : greedy version what were the pros and
- 45:56 : cons then
- 46:07 : the greedy one didn't get the right
- 46:08 : answer
- 46:10 : the
- 46:10 : greedy one can get the right answer well
- 46:12 : didn't get the right answer oh
- 46:15 : didn't get the right answer sure but but
- 46:17 : what's is there anything good about the
- 46:19 : greedy one
- 46:21 : well one advantage is just in general
- 46:23 : it's more overhead instead of hashing so
- 46:27 : you know sometimes for clarity it's
- 46:29 : better to have a simple rhythm even if
- 46:31 : it's
- 46:32 : more inefficient in practical use cases
- 46:35 : so um i think that kind of goes back to
- 46:38 : jason's
- 46:39 : point where he was talking more like
- 46:41 : technically uh in terms of like crossing
- 46:43 : that threshold
- 46:44 : you i always value readability
- 46:47 : and you know there's there's
- 46:50 : another if statement and another setting
- 46:53 : up of a table and another argument in in
- 46:56 : the uh
- 46:57 : dynamic version
- 47:00 : okay the the code complexity is more
- 47:04 : but i guess it doesn't really matter to
- 47:06 : me if the code complexity is
- 47:08 : more or less if
- 47:10 : the algorithm doesn't solve the problem
- 47:14 : right
- 47:15 : right um
- 47:18 : um
- 47:20 : well other than are you comparing the
- 47:22 : the two
- 47:24 : recursive ones like one with dynamic
- 47:26 : programming and one without are you
- 47:28 : comparing literally like the one that
- 47:30 : works and one that doesn't
- 47:32 : the one that works and the one that
- 47:35 : doesn't is there anything good about the
- 47:36 : greedy version go over this over this
- 47:40 : quote-unquote better one
- 47:42 : to be fair i think there are
- 47:44 : situations where
- 47:46 : um
- 47:47 : an algorithm that doesn't give you
- 47:50 : the always exactly correct answer could
- 47:53 : still be a good choice when you don't
- 47:56 : need
- 47:57 : exactly the correct answer
- 47:59 : um a good example is pathfinding
- 48:01 : algorithms a star is very fast but it
- 48:03 : doesn't always give you
- 48:05 : the most efficient path but it's way way
- 48:08 : way faster than something like
- 48:09 : dijkstra's which will get you
- 48:11 : the shortest path guaranteed but takes a
- 48:13 : lot longer
- 48:14 : so the benefit is speed basically
- 48:17 : right you sacrifice a little bit of
- 48:19 : accuracy for a lot of speed
- 48:22 : yeah yeah greedy still makes correct
- 48:24 : change it's not like it's going to
- 48:25 : unbalance your
- 48:26 : financial books
- 48:28 : right yeah so gritty is faster
- 48:32 : and also it uses less memory as jason
- 48:35 : already
- 48:36 : i mentioned
- 48:37 : um
- 48:39 : yeah
- 48:40 : um
- 48:43 : like like i said um i i don't
- 48:46 : i don't know if i want to go through we
- 48:48 : only have five minutes left uh i don't
- 48:50 : wanna know if like we could rewrite this
- 48:53 : using the bottom up approach as well
- 48:56 : uh for any given dynamic programming
- 48:59 : algorithm you can either write it this
- 49:02 : recursive way or write at the bottom of
- 49:04 : table based way
- 49:05 : um but since of the time i'm not going
- 49:08 : to do that
- 49:09 : and uh
- 49:11 : we will uh we'll just leave it here