989 views
0 votes
0 votes
What advantage does top down approch  have over bottom up approach in case of dynamic programming??

2 Answers

1 votes
1 votes
  • Dynamic Programming is mainly an optimization over  recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. ​​​​​​​

 

  • The idea is to simply store the results of subproblems, so that we do not have to re-comupute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

​​​​​​​​​​​​​​

  • For example, if we write simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.
1 votes
1 votes
Top down approach doesn't visit all the possible states i.e it only visits the required states .

In bottom up since we are filling the table we have to visit all the states.

So technically top down is more efficient than bottom up but there are other factors like recursion overhead for top down method .

Also top down is easy to code compared to bottom up.

EDIT :

EXAMPLE

 

Consider the case for finding binomial coefficient using this formula

nCr = n-1Cr + n-1Cr-1

Now use TOP DOWN method for finding 4C3

4C3 = 3C3 + 3C2

3C2 = 2C2 + 2C1

We stop beacuse 3C3 ,2C2 ,2C1 are all trivial cases .

Now using BOTTOM UP method you would do something like

For I = 1 to I = 4
For j = 1 to j = I
//Use bottom up Using this table filling

Here you fill values like 3C1 ,4C1,4C2 .

Notice that this values won't be calculated in top down method specified above .

Hope it helps .

Related questions

0 votes
0 votes
0 answers
1
karan25gupta asked Apr 17, 2019
675 views
In 0/1 knapsack problem ,suppose if maximum weight is given as W and we are asked to find out max profit then * IS IT NECESSARY THAT THE TOTAL WEIGHT SHOULD BE EXACTLY EQ...
0 votes
0 votes
1 answer
2
DIYA BASU asked Feb 14, 2019
477 views
Can we solve fractional knapsack using dynamic programming?
0 votes
0 votes
1 answer
3
DIYA BASU asked Feb 6, 2019
447 views
For longest common subsequence the total number of subsequence possible for the word DIYA should be 2^4 or (2^4)-1??Please explain.
2 votes
2 votes
2 answers
4
Nivedita Singh asked Dec 8, 2018
1,468 views
Is there any shortcut or Trick to get min number of multiplication faster? I mean if we could know the right split.