Fibonacci Number | Recursion + Memoization | Tabulation | DP Series | LeetCode 509

追加: 2026-05-14

[00:00:00]Hey everyone, I hope you all are safe and doing good. So in that previous lecture we have seen how to implement DP with two approaches like there are two approaches to implement DP top down and bottom up. Top down is recursion plus memorization. Bottom up is table method.

[00:00:16]So we just uh took I think a simple example of Fibonacci series and without DP first we solved with recursion simple normal recursion but what was the time complexity 2^ n exponential then we used this approach top down approach recursion we optimized recursion a little bit. So recursion plus memorization means we store the result of uh sub problems and then we reuse that result to compute the larger problem rather than computing the same sub problem again and again. Okay. Then with bottom approach with tabulation method. Okay. So now we'll submit it on code. There is a lead code question Fibonacci series. We'll submit this question there. all the three approaches DP is nothing but it's like it's like see in simple terms if I explained so if I write something like this like 1 + 1 you can simply tell me it's two then I again say 1 + 1 now if you have stored this two result somewhere now you can easily say 2 + 1 that is three so it will give me three now if I again again add 1 + 1 so now if you stored the previous result that is three so you can easily say 3 + 1 that is four then if I again say + 1 now if you stored this sum four so you can easily say 4 + 1 is 5 but if suppose you haven't stored these these sum so first 1 + 1 that will be two but I haven't stored this then 1 + 1 + 1 so again you calculate this 1 + 1 2 then + 1 3 it will give me three but you haven't stored this now again 1. So again you have to calculate first this 1 + 1 that is two then this 2 + 1 that is 3 + 1 that is four. So that is what again and again we are computing this for this sub this problem 1 + 1 again two for this again three. So that is kind of repetitive work you are doing.

[00:02:21]So rather than doing this thing we can store this intermediate results and to get the final result we can use that. So that is kind of DP okay it is just a smart way to solve some specific problems by avoiding repetitive work that's nothing but in simple terms DPS dynamic programming is the optimization technique and how that thing we have discussed with this example Fibonacci Fibonacci series this example here also there were we were solving many times this like f_sub_2 f_sub_2 f_sub_2 many times f_sub_3 f_sub_3 f_sub_3 many times. So rather than solving this many times at the very first time when we compute it just store the result just store the result and whenever later you need just reuse that result rather than recmp computing that sub problem again that is fun of dynamic programming okay I hope now idea is clear to you now let's submit this only code and then we will see later in next video one more question okay so these are just starting of DP programming Whatever we have discussed till now this Fabaki series or even the next uh lead code question also it's like hello world of DP programming hello world of dynamic programming like when we learn programming we simply learn at first how to write how to print hello world so these questions are simply hello world of dynamic programming just basics just to get you familiar with dynamic programming that's how DP works right further in for every question first we try to solve that question with recursion then with this approach then with this approach so lead code 509 it's easy uh that's the question given so uh number sum of two preceding ones starting from 0 and one that is this we know this thing and you have to calculate f of n how to write we have already done this thing so it's not tough first we just use with normal recursion down base cases so if n equal to equal to0 for n= to equal to 1. In that case, simply return whatever n is. These are two base cases. Otherwise, return what?

[00:04:38]Just call recursively for n minus one plus fib of n minus 2. That's exactly you will get because fib of 2 is f of 1 plus f of 0 previous two terms. Okay. So that's exactly we do plus previous two terms. Simply return that. So yeah that's it with normal recursion but that's not good.

[00:05:03]The time complexity is 2^ n. So it's exponential.

[00:05:07]We can optimize it.

[00:05:10]See runtime is this 9 ms. We can optimize it. How we can optimize it? Can we use here DP?

[00:05:19]How to find out that you can use here DP when the problem is we are using recursion to solve that problem? Means you are able to uh there are there are many repetitive problems same sub problems you are solving again and again. If that is the situation means they are overlapping sub problems means you can use DP. Second is optimal substructure means the optimal substructure means the sub problems have optimal solution means if the final problem has optimal solution then sub problems must have optimal solution that is optimal substructure.

[00:05:57]So this this problem Fibonacci series satisfy both those properties of DP. So we can use here DP. How to use DP? We know this thing. So we can we'll do one thing. Uh let's see I will just update this only a little bit.

[00:06:14]So there we will take one array for storing the intermediate result. So it's kind of a table. It's not simple array. It's a table. Table means only 1D array we need because only one parameter you are passing n. So we don't need 2D array or 3D array or this thing. We just need 1D array. A table is like 1D array that's so simply take an array of size n + one.

[00:06:43]Okay.

[00:06:44]And at first let's fill it with minus one.

[00:06:50]Even if you don't fill then also it will work. Let's comment this out and see it works or not. If you don't fill it without uh with minus one.

[00:06:58]Now let's call a method fib recursion and there we'll pass n plus whatever dp is whatever this array is.

[00:07:07]Yes, let's cut this out. And now we just define this method here. FIB recursion base condition.

[00:07:24]Otherwise, after checking the base condition, we check if DP of that N if it is not equal to zero.

[00:07:36]Because if you do not fill this with minus one. So by default it will be what?

[00:07:42]0 0 0 everywhere. So if it is not zero means there is some value. So simply return that value return dp of don't no need to later.

[00:07:52]Sorry it's return spelling mistake.

[00:07:57]No need to call this recursive part.

[00:08:00]Just return that DP otherwise just call this recursion. So before returning store that in that array and here also we are calling what recursively this method fib fib recus 1 n minus 2 and then return dpn now see if I run this I hope this works compilation error okay sorry the thing is because we are just passing the n minus one this n only but one more thing you have to pass dp so one more argument as dp here also that array dp now let's run see accepted every case and now you can submit now you see it will be really quick see runtime is only zero beats 100% but yeah memories we are using more because one order of n for this dp order of n for recursion stack two order of n order of n it's okay now we can optimize it that is drop down approach now we can just fill this in this specific problem we can just fill the stabulation over this array without recursion without recursion so use bottom of approach just first take the smallest problem we know the smallest problem is f of 0 is equal to 0 f of 1 is equal to 1 start from this and then move further and make f6 or f5 whatever 10 that is bottomup approach. So we fill the table or we fill this array without recursion. So that isolation method. Okay let's do this thing. Comment out this recursive approach. Same we take an array here n + one. If you want to fill it with minus one, you can fill it. Otherwise you can leave it for now.

[00:09:53]Okay. We don't have to use your recursion. Just comment out this. And we just fill we know DP is zero. At zero it will be zero.

[00:10:03]And at one place it will be one because starting two terms are 0 and one. See we have discussed this in the previous lecture. So please watch the previous lecture first then you get this code easily.

[00:10:17]Okay I have explained this thing. But there was one edge case also like if n=0 simply return zero.

[00:10:29]So please handle it.

[00:10:31]Now we taking the hurry then we do it and now we run a loop with iterative approach. Bottom up is like without recursion it's iterative. So we run the loop from two index two to i less than equal to n and i ++ at 0 and 1 index. We know the values.

[00:10:52]Now for two dp of i just fill this table. It will be sum of previous two. So I minus 1 plus whatever at I minus 2 at this index and at last we will simply return DP of N.

[00:11:15]That's it. See how simple is this. Let's run this and see.

[00:11:24]Okay, it must be return. Sorry my bad accepted and submitted.

[00:11:36]So yeah it's good but still we are taking space extra space order of n almost because one the dp we are taking.

[00:11:45]So we can optimize it in term in in terms of space as well because to get the next number we only need previous two numbers. To get the next number we only need previous two numbers. So why we store in this complete array all the numbers we just need three numbers previous one previous two and current. That's it. So okay you don't need to take this array. Let's comment out this and we just write here.

[00:12:18]Okay. So, let's comment out this also.

[00:12:22]And see this was this was the case.

[00:12:30]So, I'll just previous one previous two current and I'll just paste the same thing there.

[00:12:38]previous one previous two and n will be started I will be start from two to n just remove it this problem we have seen in the previous lecture okay so if I try to submit it let's run this and see what's what's happening okay sorry for n is equal to0 that's one edge case you have to handle this thing if n is equal equal to 0 return zero because if n is zero previous one will be zero. This will be one. We run i = 2 till less than n.

[00:13:14]So obviously this condition will not be true because i is two and n is right now zero. So 2 is not less than equal to zero. Control will go out of this for loop and it will return previous two.

[00:13:22]Previous two is right now one.

[00:13:25]So it's not true because when n is zero, it should return zero. So you can handle it. Now let's run this and see.

[00:13:36]just submit it. We have optimized now a little bit more in terms of space.

[00:13:42]Okay.

[00:13:44]So that's how we have done this this problem with I think with normal recursion with top down approach with bottom up approach plus then we optimize this basis of space as well. So almost four approaches we have seen. Okay. Now that's it for this lecture. in the next lecture. Now I'll discuss one more question on DP lead code question. So I'll see in the next lecture. Till then bye-bye. Take care.