Top-Down vs Bottom-up approach in Dynamic Programming

There are two ways to solve and implement dynamic programming problems: 1) The top-down approach and 2) The bottom-up approach. Both approaches perform similarly in one way: They use extra memory to store the solution to sub-problems, avoid the recomputation and improve the performance by a huge margin. On another side, both of them are different in so many ways, and understanding this difference would help us to make critical decisions during problem-solving.

How top-down( approach works?

In the top-down approach, we implement the solution naturally using recursion but modified to save the result of each subproblem in an array or hash table. This approach will first check whether it has previously solved the subproblem or not. If yes, it returns the stored value and saves the further calculation. If not, it will calculate the value in the usual manner. We say that it is the memoized version of a recursive solution, i.e., remembers” what results have been calculated previously.

Visualization: Finding the 5th Fibonacci using top-down approach

Finding Fibonacci using top-down approach

How bottom-up approach works?

On another side, the bottom-up approach is just reverse but an iterative version of the top-down approach. It depends on a natural idea: the solution of any subproblem depends only on the solution of “smaller” subproblems. We sort the subproblems by size and solve them in the order of smallest to largest. When solving a particular subproblem, we have already solved all of the smaller subproblems its solution depends upon, and we have saved their solutions. In other words, we solve each sub-problem only once, and when we first see it, we have already solved all of its smaller subproblems.

Visualization: Finding the 5th Fibonacci using bottom-up approach

Finding Fibonacci using bottom-up approach of dynamic programming

Here are some critical differences

  • Top-down is a recursive problem-solving approach but bottom-up is an iterative problem-solving approach. In other words, the top-down approach assumes the subproblems will be solved using the smaller sub-problem only once using the recursion. In a reverse way, bottom-up compose the subproblems’ solution iteratively using the smaller sub-problems.
  • Most of the time, top-down approach is easy to implement because we just add an array or a lookup table to store results during recursion. But in the bottom-up approach, we need to define an iterative order to fill the table and take care of several boundary conditions.
  • The top-down approach is slower than the bottom-up approach because of the overhead of the recursive calls. In other words, the bottom-up approach often has much better constant factors since it has no overhead for recursive calls.
  • The top-down approach has also the space overhead of the recursion call stack. If the recursion tree is very deep, we may run out of stack space, which will crash your program.
  • Asymptotically, both of these approaches guarantee the same time complexity, except in unusual circumstances where the top-down approach does not actually recurse to examine all possible subproblems.
  • The top-down approach starts from the large input size problem, reaches the smallest version of the problem (Base case), and stores the subproblem solutions from the base case to the larger problem. But in the bottom-up approach, we first store the solution for the base case and store the subproblem solutions in a particular order from the base case to the larger sub-problem.
  • With the bottom-up approach, sometimes, there is scope to optimize the time and space complexity further. We can try to reduce one loop or try to save space from O(n²) to O(n) or O(n) to O(1). But such types of optimization are challenging to achieve in a top-down approach.

Enjoy learning, Enjoy algorithms!

More From EnjoyAlgorithms

Our weekly newsletter

Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.

Follow Us:

LinkedinMedium

© 2020 EnjoyAlgorithms Inc.

All rights reserved.