Hi! Welcome to GeeksforGeeks. In previous two videos, we discussed the properties

of Dynamic Programming problems and the Memoization technique. In this video, we will discuss the Tabulation

technique. In Tabulation, we build the lookup table in

bottom up fashion, i.e., we begin with solutions to the base problems and use them to calculate

solutions to higher problems. And, after the table is built, we return the

required value, say, table[n]. Let’s understand the algorithm now. First, we enter the base value of ‘i’

in the lookup table. Then, we run a loop that iterates over the

remaining values of ‘i’. At every iteration ‘i’, we update the

ith entry in the lookup table by using the solutions to the previously solved subproblems. After the loop ends, we return the value table[n]. As simple as that. Let’s see how Tabulation will work for our

Fibonacci Number problem. First, we enter the base values in the lookup

table. Now, we run a loop for the remaining values

of ‘i’ in order to fill the rest of the table. We update table[2] as 1, table[3] as 2, table[4]

as 3, and finally, table[5] as 5. And, done. So, we see, unlike memoization where the program

control was jumping from one function call to another function call, we got it all done

in a single function call. This makes it look like Tabulation might be

better than Memoization. But, is it always the case? Since Tabulation works in bottom up fashion,

it computes solutions to all the subproblems. However, it avoids performing multiple checks

and lookups. When compared to the memoized version, this

often saves function call overhead time. On the other hand, since Memoization works

in top down fashion, it computes solutions to subproblems on demand. So, in the worst case, Memoization solves

all the problems but, in the best case, it does not. But, Tabulation always solves all the problems. Also, sometimes, the Memoization solution

is more intuitive to come up with than its Tabulation counterpart. We will discuss these points in more detail

later. Let’s now shift our focus to the C code. First, we declare our lookup table. Then, we enter the base values. And, then we fill the table for the remaining

values of ‘i’. Finally, we return the required value f[n]. That’s all for now. Thank you for watching!

You have made programmers life simpler 🙂 Thanks a lot.

what does do exactly running a loop and fill the values. can you explain it more clearly, lets say we have to calculate fibnacci value for value 6. How do we fill the values in table first and then use them. Thanks in Advance.

if iam a prime minister of india i ll make geeks fo geeks as the top educational system.and i ll fund lots of crores to it. ilove u geeks for geeks thank u very much . very beatiful site too..we love u geeks for geeks guys

Hi correct me if i am wrong ! but in case of tabular form why do we storing values when we can clearly compute the value using the for loop only without storing the values in array ? ?

Nice work

the computation for 50th fibonacci number is taking too long i.e. approx 219 to 250 seconds to give result even on going by dp approch

Excellent tutorial.

Hi, good knowledge ..

Actually I need your advice .I am Android developer ,so I need to improve my logics ,I had already check many links and site's .but I can't understand the proper sense of knowledge ,how can I improve my logic ,plz help me,

Please Please Please slow down GFG ..sometimes it is hard to catch you guys.

I expected you to go more in Tbulation or Memoization slide .Please do it

If u r speaking in English no need of giving subtitles

Can we use "int f[n+1];" ?

An array is a static data type, so its maximum memory should be declared at compile time and not during runtime.

You had me at 00:34 "… loop that iterates over the remaining values of i". You just initialized the base value of i so how is it possible to iterate over remaining?

plzzzzz upload more videos in dp and ds