Dynamic Programming | Set 1 (Solution using Tabulation) | GeeksforGeeks


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!

14 thoughts on “Dynamic Programming | Set 1 (Solution using Tabulation) | GeeksforGeeks

  1. 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.

  2. 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

  3. 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 ? ?

  4. 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

  5. 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,

  6. 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.

  7. 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?

Leave a Reply

Your email address will not be published. Required fields are marked *