Dynamic Programming Tutorial with Fibonacci Sequence

Key Takeaways

hey guys this is my introduction to dynamic programming with Fibonacci Sequence as our example now what's fibon sequence it's a sequence of numbers that start with ones at the beginning two ones at the beginning and after that we just add the previous two numbers to get the next number so 1 + 1 = 2 and 1 + 2 = [Music] 3 and 2 + 3 = 5 and so on and the problem here is finding the nth Fibonacci number so if n is six the six Fibonacci number is 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 fib 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 six fibon number to do that in this approach what we do is we ask ourselves what's the fifth F number number and what's the fourth FIB not number and when we know what they are we add them together to find the sixth fibon Notch number and to find the fifth Fage number we need to find the fourth fan number the third Fage 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 computation for instance to find the third fiban number we're repeating the same process three times and to find the fourth fibon number we're repeating the same competion twice and that's why this is very slow and in fact the time it takes to find the n f number is about an order of 2 to the^ 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 simplic s and let's just say we're trying to find the six fibach 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 negative 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 element here to n minus one which corresponds to the last element 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 + 1 = 2 and for the fourth element we get 1+ 2 = 3 and five and so on and at the end we're just going to return the last element in the array which is eight in this case this is a much better solution than the previous solution to find N's fibon 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 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 subarray problem for which you can also use a dynamic uh 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