What is Dynamic Programming?
The term Dynamic Programming was coined to describe the approach of planning and optimally finding the solution of a multi-staged problem.
Dynamic Problems deals with division of problems into sub-problems and then finding the solutions of these sub-problems to reach the solution.
You might be thinking then what is the difference between Dynamic Programming and Divide and Conquer approach?
Let us understand with a diagram. Basic difference between Divide Conquer and Dynamic Programming is that in Divide Conquer the sub-problems are independent problems, while in case of Dynamic Programming they are dependent on each other. Hence the results of the existing sub-problems are re-used.
Steps to Solve a Dynamic Programming problem:
1. Analyse and Divide the problem into sub-problems.
2. Check if the solution of the sub-problem exists.
3. If the Solution exists then use it, otherwise find the solution for the sub-problem and store it.
Dynamic Programming approach is applicable to a lot of problem’s. Some of the common problems are:
1. Longest Sub-string.
2. Subset Sum Problem.
3. Longest Increasing Subsequence.
That’s all for now stay-tuned for more …
In upcoming blogs we will show how to approach the above problems using Dynamic Programming