self doubt

Question

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

Comments

According to me following any approach depends on the type of problem. We can't say Top Down approach is better in terms of accessing or something and Bottom up approach does not. So it must depends on what is the type of problem and what will be suitable to solve it.

---

The key to solving dynamic programming is think top to bottom i.e in terms of sub-problems but actually solve the recurrence bottom to top.

Answer 1

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

Comments

@Doraemon

And all algorithms solved greedily can be solved dynamically but not viceversa.

r u sure about it? 

---

https://stackoverflow.com/questions/16690249/what-is-the-difference-between-dynamic-programming-and-greedy-approach

---

I think yes because all problems can be represented recursively.so DP can be applied  and if we donot have overlapping subproblems then it would take the same time as recursion takes.

Answer 2

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 .

Comments

@ashunimbz 

Top down approach doesn't visit all the possible states i.e it only visits the required states 

Please give an example.