Dynamic Programming

What is Dynamic Programming

In the dynamic programming or DP approach, the subproblems are broken down into smaller sub-problems. These sub-problems are solved, and results are remembered to solve the similar or overlapping sub-problems. These sub-problems are combined in order to get the best solution. 

Richard Bellman developed the dynamic programming or DP method in the 1950s, and it is being used in numerous fields, from aerospace engineering to economics. The core concept of dynamic programming was to avoid repetitive tasks by remembering the partial output of the previous problem. These concept applications are widely used in real-life situations. 

Approaches of Dynamic Programming

Dynamic programming uses two approaches :

1. Top-down Approach : This approach is based on the memorization technique. It solves sub-problems whenever required and can be easily debugged. Memorization technique is the combination of recursion and caching, where recursion is calling the function by itself and caching means storing the intermediate results. This process requires more memory in the call stack and sometimes stack overflow conditions may occur if the recursion is too deep.

2. Bottom-up Approach : This approach is based on the tabulation or table filling method. It solves the problem of stack overflow by avoiding the recursion and saving memory space. In this approach, we solve the sub-problems first and then move to a larger problem by using smaller sub-problems. The results are stored in form of the matrix.

Steps of Dynamic Programming

1. Break down larger problems into smaller sub-problems.

2. Find the optimal solutions for these sub-problems.

3. Stores the results of sub-problems. This process is known as memorization.

4. Reuse the same sub-problems so that similar sub-problems can be calculated more than once.

5. At last, calculate the result of the larger problem.

These are the basic steps used in dynamic programming. The dynamic programming is applicable if the problems have overlapping sub-problems and optimal substructures properties.

Famous Dynamic Programming algorithms are:

• Unix diff : For comparing two files

• Bellman-Ford : For finding shortest path routing in networks

• TeX : The ancestor of LaTeX

• WASP : Winning and Score Predictor

Characteristic of Dynamic Programming

1. Overlapping Sub-problems : It is used when the same sub-problem needs to be calculated again and again. Dynamic Programming is used to store the results of sub-problem and we don’t need to recompute them again and again. Dynamic Programming is not used when overlapping sub-problems are not there and results are not needed to store in the tables.

2. Optimal Substructure: A problem is said to be an optimal substructure if its all optimal solution can be calculated from its optimal solution of sub-problems. 

Example of Dynamic Programming

The following problems can be solved using the dynamic programming approach :

• Fibonacci number series

• Project scheduling

• Shortest path by Dijkstra

• All pair shortest path by Floyd-Warshall

• Knapsack problem

• Tower of Hanoi

Advantages of Dynamic Programming

1. Dynamic Programming can easily solve problems in chemical engineering design, inventory, control theory, etc.

2. Need not calculate same problems again and again. 

3. Suitable for multi-point, multi-stage or sequential decision processes.

4. It saves memory space by overwriting the updated values of sub-problems.

5. Well suited for discrete or continuous variables, linear or non-linear problems, and deterministic problems.

Disadvantages of Dynamic Programming

1. Difficult to develop code because DP has different methods to solve.

2. The recursive method takes lots of memory for storing.

3. Have slow execution speed.

4. The large problems are divided into sub-problems, and results are stored that consume lots of space.