Ad Code

What Is Dynamic Programming

 Hello friends! In this post, I will discuss about Dynamic Programming. In the journey of learning  Data Structures and Algorithms, this is one of the most difficult concept for many people. You have to do lots of practice along with having a solid understanding of theoretical concepts to make a strong grip on this. 
That's said, let us start, Dynamic Programming is an algorithmic paradigm that comprises two processes:
a. Break a big problem into small small chunks, (we call them subproblems) and use their solutions to reach the solution of the big problem.
b. Store the solution of every subproblem somewhere (Such as array, matrix, etc.) to avoid the repeatative calculations.

    These are the two processes with the help of which we solve a problem using Dynamic Programming paradigm. But, now next questions is, Can we solve every problem using this paradigm. The answer is No. Some problems are there only, where we can use this paradigm. So, the first thing is to identify if the given problem can be solved using Dynamic Programming or not. Now, how to identify them. There are only two main properties of a problem that suggests that the given problem can be solved using Dynamic programming,
1. Optimal Substructure
2. Overlapping Subproblems

1. Optimal Substructure: A problem is said to be having this property if its optimal solution can be obtained from the optimal solutions of its subproblems.

2. Overlapping Subproblems: It means, solution of every subproblem is needed again and again. So, to reduce the cost of repeatative computations, we store the solution of every subproblem somewhere; e.g.,  array, matrix, etc. 

    A very important point to note here that in Divide and Conquer algorithm also, we need to combine the solution of subproblems to get the solution of bigger problems, i.e., We can use Divide and Conquer algorithm to solve the problem having only Optimal Substructure property. But, if the problem is having both the above mentioned properties, then, it is better to use Dynamic Programming.