hey CS dojo its YK here so in this video
I'm going to talk about what dynamic
programming is and how to use it and as
I explain how it works I'm going to
assume that you're already familiar with
recursion so what is dynamic programming
exactly it's actually fairly simple even
though it might sound difficult it's
basically a way of making your algorithm
more efficient by storing some of the
intermediate results and it works really
well when your algorithm has a lot of
repetitive computations so that you
don't have to repeat those competitions
over and over again and I'm gonna give
you a concrete example of how it works
with Fibonacci sequence so just in case
you're not familiar with it phonology
sequence is a sequence of numbers that
starts with two ones at the beginning
and each number after that is computed
by adding up the two previous numbers so
the third three months number is two
because one plus one equals two and then
the fourth 300 number is three because
one plus two equals three and so on and
this sequence keeps on going forever so
let's say we're trying to solve the
problem of finding the entrance number
or writing a function called fib of n
which takes a positive integer n and
finds and returns the end speedruns
number so if the given n is three we
want to be able to find and return the
third Finch number which is two and if
the given n is five we want to be able
to return the fifth Reynolds number
which is five let's see how we can solve
this problem using dynamic programming
so if you want to solve a problem using
dynamic programming there are typically
three steps you can take the first step
is to come up with a recursive solution
to your problem and then in your
recursive solution if you notice that
there are a lot of repeated competitions
you can then store some of the
intermediate results so that you don't
have to repeat those competitions this
process is also called memoization or
memorize and this is not to be confused
with memorize and I've made a mistake
before too and then the third step if
you don't like using recursion anymore
is to come up with something called a
bottom-up approach so let's first see
what a recursive solution might look
like for this particular problem so as I
said earlier we're going to write a
function called fable of n which takes
and a positive integer and returns the N
3 branch number and if n is equal to 1
or 2 we know that the first and the
second finish numbers are 1 we're going
to return 1 but instead of returning it
right away
we're going to store it in a temporary
variable called the result and then
return that instead and it's going to be
clear why we need to do that later and
if n is neither one nor two then we're
going to return the sum of the two
previous Fibonacci numbers instead fib
of n minus 1 plus fib of n minus 2 store
that in result and then return it at the
end so the solution works but it's very
very inefficient to see why let's see an
example where we're trying to find the
5th Fibonacci number by calling table 5
so to find the return value of people 5
we need to first compute the return
values for table 4 and people 3 so we
can add them up and to find people for
we need to first compute fib of 3 and
peep of 2 and so on and that's what this
diagram shows and looking at this
diagram you might notice that there are
some competitions that we repeat over
and over again for example we need to
compute the return value for people to
three times and we need to compute the
return value for fib of 3 twice here and
it's not a big deal when we are trying
to find the fifth or sixth minus number
but if we're trying to find the
hundredth free bonus number it becomes
an issue and actually the time it takes
to find the nth Fibonacci number grows
exponentially or roughly in the order of
two to the power of n and dynamic
programming here says why not just store
those return values for example for fib
of 3 store the return value once we
compute it and then use that same value
when we see people 3 again in
instead of computing it again and again
this process is called memoization so
let's see what a memorized solution
looks like in code let's again consider
the example where we're trying to find
the fifth boomers number by calling
people five the idea of this solution is
going to be that we're going to use an
array whose length is n plus one or six
in this particular case because n here
is five and then we're going to store
the return value for the function of fib
of n at the index n so we're going to
store feeble of one which is the first
few months number right here at index 1
and then fib of 2 at index 2 and so on
and initially we're going to set all
these values to now and we're going to
write our function of fib and this is
going to take two arguments instead of
just one the first one is the same as
before and a positive integer and the
second one is going to be this array and
so you need to initialize the survey
memo before you call this function now
at the beginning of this function check
if memo at index n is null or not if
it's not equal to now that'll mean that
we've already seen this argument N and
we've already stored the return value
for that at the index n a memo so just
return that instead so we turn memo
square brackets and otherwise the
following part is the same as before if
n is equal to 1 or 2 we turn one store 1
in result and then return that at the
end and if that's not the case then find
the sum of the two previous fabulous
numbers and then return that instead and
then what's new in this function is that
before you return this result the return
value you need to store it in memo at
index n so that you can use it later
now let's now think about the time
complexity for the
solution we're going to call it T of n
this is going to be the time it takes to
find the nth Fibonacci number with this
particular method and we're going to
find that by multiplying the number of
times we call this function baby with
the time it takes to execute each of
those calls we're going to call that T
now there are only two ways we're going
to call this function of fib the first
way is when we call this function for
the first time with the arguments and
and memo to find the NSP ones number and
the second way is from this line right
here and notice that if you look at this
whole block after this first if clause
this whole block is only executed most n
times and this is true because there are
n possible arguments to this function
that's 1 through N and each time this
function is called with each of those
arguments the return value will be
stored a memo at index n so after the
first time this function is called with
each argument we'll never get to this
block and each time this block is
executed fib is called a most twice if
we get to this line so the number of
times fib is called is at most two times
n plus 1 so 2 n it comes from this block
right here and one comes from the first
time we call this function fib and the
time it takes to execute each of those
calls this T right here is going to be a
constant time or a Big O of 1 and this
is because if you look at each operation
in this function excluding these
recursive calls that follow each
operation is a constant time operation
and when you have a constant time
operation when you add them up you still
get a constant time operation
which is big-oh of one and that's why we
have Big O of one here and so T of N or
the time it takes to find the nth
feminist number with this particular
method is going to be 2 n plus 1 times
Big O of 1 which is Big O of 2 n plus 1
which is equal to Big O of N and this is
a huge improvement from what we had
earlier which was Big O of 2 to the
power of n now let's now examine how
this memo array is actually filled so
let's say we're trying to find the 5th
Fibonacci number again and when we call
fib with the argument 5 and memo of
course we'll see that we don't have a
stored value at the index 5 yet so we go
down and we're going to ask ourselves
what's the value of fib of 4 and then 3
and so on and when we get to fever of 2
we'll know that this value is 1 so we're
gonna store it at index 2 right here and
same with people 1 that's 1 right here
and once we have these two values we'll
be able to find the third a Fibonacci
number which is fib of 3 right here and
then once we find the value by adding
them up store that value right here so
we can use it later and then when we go
up to feeble 4 we'll add 1 and 2 right
here and we get 3 and so on until we get
here and so as you can see this array is
mostly filled from left to right so when
you see this you might say why not just
explicitly build this array from left to
right from scratch instead of building a
recursively and that's the idea behind a
bottom-up approach so let's see what a
bottom-up approach might look like in
code we're going to define a function
called fab bottom-up which takes an a
positive integer just like before and
returns the nth Fibonacci number and
then if n is equal to 1 or 2 of course
we're going to return 1 and after that
we're going to define an array whose lie
is going to be n plus 1 where n plus 1
is 6 of course if we're trying to find
the fifth Fibonacci number right here if
n is equal to five and after that we're
going to set the first and the second
elements of this array bottom up to be 1
these two items right here and then
we're going to run a for loop for I from
3 which corresponds to this item right
here up to N and n corresponds to the
last item right here of this array and
whatever index we're examining currently
we're going to set that element at the
index I or bottom up square brackets I
to be the sum of the two previous items
so in this particular example we'll have
two here three here and after that we're
going to return the last item in bottom
up or bottom up square brackets N and
we're done the time complexity for this
algorithm will be again Big O of n
because we're going to define this array
and go through this array only once
ok so that's how dynamic programming
works but now I'm going to show you a
quick demo with Python and something
called Jupiter notebook to show you how
this idea of my play out in practice so
in this jupiter notebook i have defined
a few functions in Python fib of n which
is a recursive naive recursive solution
and river of memo and people to which
represent a memorized solution and fifth
bottom up which is of course a bottom up
solution so let's see how they compare
to each other in performance we're gonna
try running fib of n first the naive
recursive solution with fever five and
that gives us 5 which is expected what
about fever of 20 that gives us the
answer pretty quickly - and what about
fever of 35 this actually takes five to
six seconds on my computer so it's
obviously not the most efficient
approach let's see how fib of 2 and 3
both memo the memorized solution
compares to that let's try running fifth
memo of 5
first and that gives us five which is
expected and what about 50 mm or 35
that's pretty quick - and what about 50
ml 100 and 1000 this actually gives us
an error and this error is called a
recursion error Python gives us this er
actually because there are too many
recursive calls on a call stack and to
fix that we can just use the bottom-up
approach one advantage of using a
bottom-up approach is that we don't have
to put any recursive calls on a call
stack so we don't have to worry about
that so we're going to load this
function and then run it with the
argument 35 which is pretty quick 1000
and then let's try 10,000 as well and
that's pretty instantaneous - okay so
that's my introduction to dynamic
programming let me know in the comment
section below what you thought of this
video and if you have any requests about
what kind of videos I should make in the
future let me know in the comment
section below as well
I'm YK from CES dojo and I'll see you in
the next video