Wednesday 19th February 2025
Dynamic Programming
By Simplyhawk

Dynamic Programming

Dynamic Programming is an algorithmic technique with the following properties.

It is mainly an optimization over plain recursion. Wherever we see a recursive solution with repeated calls for the same contributions, we can optimize it using Dynamic Programming.

The idea is to store the grades of subproblems so that we do not have to re-compute them when needed later. This humble optimization typically reduces time complexities from exponential to polynomial.

Some widespread problems solved using Dynamic Programming are Fibonacci Numbers, Diff Utility (Longest Common Subsequence), Bellman-Ford Shortest Path, Floyd Warshall, Edit Distance, and Matrix Chain Multiplication.

How Does Dynamic Programming Work?

Dynamic programming works by breaking down multifaceted problems into simpler subproblems. Then, finding optimal answers to these subproblems. Memorization is a technique that saves the outcomes of these procedures so that the corresponding answers do not need to be computed when they are later wanted. Saving solutions saves time when computing subproblems that have already been encountered.

Dynamic programming can be achieved using two approaches:

  1. Top-down approach

In computer science, problems are resolved by recursively formulating solutions, employing the answers to the problems’ subproblems. If the answers to the subproblems overlap, they may be memoized or kept in a table for later use. The top-down approach follows the strategy of memorization. The memoization process is equivalent to adding the recursion and caching steps. The difference between recursion and caching is that recursion requires calling the function directly, whereas caching requires preserving the intermediate results.

The top-down strategy has many benefits, including the following:

The top-down approach is easy to understand and implement. In this approach, problems are broken down into smaller parts, which help users identify what needs to be done. With each step, more significant, more complex problems become smaller, less complicated, and, therefore, easier to solve. Some parts may even be reusable for the same problem.

It allows for subproblems to be solved upon request. The top-down approach will enable problems to be broken down into smaller parts and their solutions stored for reuse. Users can then query solutions for each part.

It is also easier to debug. Segmenting problems into small parts allows users to follow the solution quickly and determine where an error might have occurred.

Disadvantages of the top-down approach include:

The top-down approach uses the recursion technique, which occupies more memory in the call stack. It leads to reduced overall performance. Additionally, when the recursion is too deep, a stack overflow occurs.

  1. Bottom-up approach

In the bottom-up method, once a solution to a problem is written in terms of its subproblems in a way that loops back on itself, users can rewrite the problem by solving the smaller subproblems first and then using their solutions to solve the larger subproblems.

Unlike the top-down approach, the bottom-up approach removes the recursion. Thus, there is neither stack overflow nor overhead from the recursive functions. It also allows for saving memory space. Removing recursion decreases the time complexity of recursion due to recalculating the same values.

The advantages of the bottom-up approach include the following:

It makes decisions about small reusable subproblems and then decides how they will be put together to create a significant problem.

It removes recursion, thus promoting the efficient use of memory space. Additionally, this also leads to a reduction in timing complexity.

Conclusion

We have learned that dynamic programming is not a specific design design as it is a way of thinking. Its goal is to create an answer to preserve previously seen values to increase time efficiency. While examples include basic algorithms, dynamic programming provides a foundation in almost all programs. It includes the use of simple variables and complex data structures.

  • No Comments
  • January 22, 2025