Dynamic Programming

Dynamic Programming

Dynamic programming is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems. the concept behind dynamic programming is to break the problems into sub-problems and save the result for the future so that we will not have to compute that same problem again. Further optimization of sub-problems that optimizes the overall solution is known as optimal substructure property.

There are two ways in which dynamic programming can be applied:

Top-Down:

In this method, the problem is broken down and if the problem is solved already then the saved value is returned, otherwise, the value of the function is memoized i.e. it will be calculated for the first time; for every other time, the stored value will be called back. Memoization is a great way for computationally expensive programs. Don’t confuse memoization with memorization.

Memoize != memorize

Bottom-Up:

This is an effective way of avoiding recursion by decreasing the time complexity that recursion builds up (i.e. memory cost because of recalculation of the same values). Here, the solutions to small problems are calculated which builds up the solution to the overall problem. (You will have more clarity on this with the examples explained later in the article).

Understanding Where to Use This Technique

As mentioned above, if you notice that the problem can be broken down into sub-problems and these can be broken into much smaller ones and some of these have overlap (i.e. requires the computation of previously calculated values). The main goal is to optimize the code by reducing the repetition of values by storing the results of sub-problems.

Recursion and Dynamic Programming

Recursion is a way of finding the solution by expressing the value of a function in terms of other values of that function directly or indirectly and such function is called a recursive function. It follows a top-down approach.

Dynamic programming is nothing but recursion with memoization i.e. calculating and storing values that can be later accessed to solve subproblems that occur again, hence making your code faster and reducing the time complexity (computing CPU cycles are reduced).

Recursion takes time but not space, while dynamic programming uses space to store solutions to subproblems for future reference thus saving time.