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 recomputation and improve 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.
In the top-down approach, we implement the solution naturally using recursion but modify it to save the solution of each subproblem in an array or hash table. This approach will first check whether it has previously solved the subproblem. If yes, it returns the stored value and saves further calculations. Otherwise, top-down approach will calculate sub-problem solutions in the usual manner. We say it is the memoized version of a recursive solution, i.e., it remembers what results have been computed previously.
Visualization: Finding the 5th Fibonacci using top-down approach
On another side, bottom-up approach is just the reverse but an iterative version of the top-down approach. It depends on a natural idea: solution of any subproblem depends only on the solution of smaller subproblems. So bottom-up approach sorts the subproblems by their input size and solves them iteratively in the order of smallest to largest. In other words, when solving a particular subproblem, bottom-up approach will first solve all of the smaller subproblems its solution depends upon and store their values in extra memory.
Visualization: Finding the 5th Fibonacci using bottom-up approach
Enjoy learning, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.