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