hey guys this is my introduction to
dynamic programming with people notches
sequence as our example
now what's fibonacci sequence it's a
sequence of numbers that start with ones
at the beginning - ones at the beginning
and after that we just add the previous
two numbers to get the next number so
one plus one equals two and one plus two
equals three and two plus three equals
five and so on and the problem here is
finding the nth Fibonacci number so if n
is six the sixth Fibonacci number it's
just eight the most naive approach we
can think of for this problem is a
recursive one so in this code I'm
defining my function here if Abe and if
n is equal to one or two we just return
one which is base case and that
corresponds to the first two elements
and if that's not the case we're just
going to return the sum of the previous
element and the second previous element
so this approach works but the thing is
this is very very inefficient let's see
why that's the case
here's a quick analysis of the naive
recursive approach that we just talked
about let's just say as an example we
are trying to find the sixth Fibonacci
number to do that in this approach what
we do is we ask ourselves what's a
15-month number and what's the fourth
field nuts number and when we know what
they are we add them together to find a
60ms number and to find the fifth
Fibonacci number we need to find for
three months number the third few
minutes number and then add them
together that's what this diagram shows
and as you can see the problem with this
approach is that there are a lot of
duplicates in our competition for
instance to find a third Fibonacci
number we're repeating the same process
three times and to find the fourth
Fibonacci number we're repeating the
same competition twice and that's why
this is very slow and in fact the time
it takes to find the nth Fibonacci
number is about an order of two to the
power of n
and dynamic programming says we can do
much better than that just by storing
all those intermediate results so here's
one very simple dynamic programming
solution in this example we're going to
assume that N is larger than two just
for simplicity sake and let's just say
we're trying to find the sixth Fibonacci
number as our previous example and the
first thing we do is we initialize an
array of the same size as the given
number and we are initializing it to
zeros here but it doesn't matter if we
initialize it to ones or nearly ones and
obviously the first two elements need to
be one and we're going to iterate this I
from two which corresponds to the third
demand here 2n minus 1 which corresponds
to the la semaine here and for each i
we're going to populate it with the sum
of the previous number and the second
previous number so for the third element
we get 1 plus 1 equals 2 and for the
fourth element we get 1 plus 2 equals 3
and 5 and so on and at the end we're
just gonna return the last element in
the array which is 8 in this case this
is a much better solution than the
previous solution to find nth Fibonacci
number
it only takes a linear time so it's much
faster but you might say oh but we are
using all this extra space and if you
don't like that
that's fine you can just store the last
two elements instead of everything and
you can save some space that way as well
that's it for my video if you like this
video you might also like my video about
the maximum sub array problem for which
you can also use a dynamic programming
solution and if you want to watch more
videos like this one you can just click
right here to subscribe to my channel
and see you soon