Many computational problems are solved using a divide-and-conquer approach recursively. In these problems, we see an optimal substructure. That is, we find ourselves solving the same sub-problem over and over.
An example is the recursive computation of the nth Fibonacci number.
There are two approaches in dynamic programming that we can use to solve the problems:
- Top-down approach with memoization
- Bottom-up approach with tabulation
In the top-down approach, we store all the results of solved subproblems in an array or hash map and use them wherever we encounter an overlapping subproblem during the recursion.
The bottom-up approach allows us to not use recursion as we used it in the top-down approach. The bottom-up approach uses an n-dimensional array to store the results of solved subproblems and use it whenever we encounter an overlapping subproblem.
Real-world problems#
Many problems in the real world use the dynamic programming pattern. Let’s look at some examples.
- Load Balancer: Find the optimal way to handle a given workload by using servers with different workload handling capacities.
- Search Engine: Check if white spaces can be added to a query to create valid words in case the original query does not get any hits on the web. Find all the possible queries that can be created by adding white spaces to the original query.
