Dynamic Programming is a programming technique in which we breakdown a complex problem into smaller sub-problems. The idea to to divide a problem into smaller sub-problems and use the solutions of these smaller sub-problems to reach to the solution of our original problem. It follows the divide-and-conquer paradigm of programming.
Where can we apply dynamic programming?
Speaking in technical terms, dynamic programming can be applied to problems have "overlapping-sub-problems" and "optimal-sub-structure".
Now the question arises what are these terms and how does dynamic programming take advantage of that ?
Overlapping-sub-problems :
A problem is said to have overlapping-sub-problems if the problem can be broken down into sub-problems which are reused several times.
While following the naive approach generally, we will see that some sub-problems are generated and solved many times in our solution. So we can take advantage of this fact. We can save the answer for a sub-problem once it is calculated. The next time the same sub-problem arises, we can look up for the saved value. This technique is called "memorization". In this way, we solve each sub-problem only once and thus reduce the number of computations.
Optimal-sub-structure :
A problem is said to have an optimal-sub-structure if an optimal solution can be constructed effectively from the optimal solutions of its sub-problems.
This was a glimpse of Dynamic Programming. It is logical and so you will understand better by reading few examples in the next posts.
Where can we apply dynamic programming?
Speaking in technical terms, dynamic programming can be applied to problems have "overlapping-sub-problems" and "optimal-sub-structure".
Now the question arises what are these terms and how does dynamic programming take advantage of that ?
Overlapping-sub-problems :
A problem is said to have overlapping-sub-problems if the problem can be broken down into sub-problems which are reused several times.
While following the naive approach generally, we will see that some sub-problems are generated and solved many times in our solution. So we can take advantage of this fact. We can save the answer for a sub-problem once it is calculated. The next time the same sub-problem arises, we can look up for the saved value. This technique is called "memorization". In this way, we solve each sub-problem only once and thus reduce the number of computations.
Optimal-sub-structure :
A problem is said to have an optimal-sub-structure if an optimal solution can be constructed effectively from the optimal solutions of its sub-problems.
This was a glimpse of Dynamic Programming. It is logical and so you will understand better by reading few examples in the next posts.
No comments:
Post a Comment