562 views
1 votes
1 votes

Why we need to do top-down and bottom-up these 2 approach in dynamic programming? I know bottom-up has better overhead. Then why not bottom up used everywhere? Both have time complexity $O(n^{2})$ right?

Plz analysis these two algo for more clearity

top-down

bottom-up

1 Answer

Best answer
3 votes
3 votes
Actually, there are two ways to approach the same problem using Dynamic Programming.

But the problem with the top-down approach is that it requires recursion, thus not very efficient for large inputs as it will blow up the stack. Also, the top-down approach starts with the bigger problem which can't be calculated until answer to smaller subproblem is known, thus lots of push is performed on the stack for large inputs.

On the other hand in the bottom-up approach, we start with smaller subproblem, such that when we calculate the larger problem, answers to smaller subproblem is already known. Therefore no need of stack.

Hence, Dynamic Programming always uses the bottom-up approach.
selected by

Related questions