Intro to Dynamic Programming

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.

Transcript

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