Home » Algorithms

Dynamic Programming (Components, Applications and Elements)

In this article, we will learn about the concept of Dynamic programming in computer science engineering. Approach for solving a problem by using dynamic programming and applications of dynamic programming are also prescribed in this article.
Submitted by Abhishek Kataria, on June 27, 2018

Dynamic programming

• Dynamic programming is an optimization method which was developed by Richard Bellman in 1950.
• Dynamic programming is used to solve the multistage optimization problem in which dynamic means reference to time and programming means planning or tabulation.
• Dynamic programming approach consists of three steps for solving a problem that is as follows:
  1. The given problem is divided into subproblems as same as in divide and conquer rule. However dynamic programming is used when the subproblems are not independent of each other but they are interrelated. I.e. they are also called as overlapping problems.
  2. To avoid this type of recomputation of overlapping subproblem a table is created in which whenever a subproblem is solved, then its solution will be stored in the table so that in future its solution can be reused.
  3. The solution of the subproblem is combined in a bottom of manner to obtain the optimal solution of a given problem.

Components of Dynamic programming

1. Stages
   The given problem can be divided into a number of subproblems which are called stages. A stage is a small portion of given problem.
2. States
   This indicates the subproblem for which the decision has to be taken. The variables which are used for taking a decision at every stage that is called as a state variable.
3. Decision
   At every stage, there can be multiple decisions out of which one of the best decisions should be taken. The decision taken at each stage should be optimal; this is called as a stage decision.
4. Optimal policy
   It is a rule which determines the decision at each and every stage; a policy is called an optimal policy if it is globally optimal. This is called as Bellman principle of optimality.

Applications of dynamic programming

1. 0/1 knapsack problem
2. Mathematical optimization problem
3. All pair Shortest path problem
4. Reliability design problem
5. Longest common subsequence (LCS)
6. Flight control and robotics control
7. Time sharing: It schedules the job to maximize CPU usage

Elements of dynamic programming

Dynamic programming posses two important elements which are as given below:

1. Overlapping sub problem
   One of the main characteristics is to split the problem into subproblem, as similar as divide and conquer approach. The overlapping subproblem is found in that problem where bigger problems share the same smaller problem. However unlike divide and conquer there are many subproblems in which overlap cannot be treated distinctly or independently. Basically, there are two ways for handling the overlapping subproblems:
   1. Top down approach
      It is also termed as memoization technique. In this, the problem is broken into subproblem and these subproblems are solved and the solutions are remembered, in case if they need to be solved in future. Which means that the values are stored in a data structure, which will help us to reach them efficiently when the same problem will occur during the program execution.
   2. Bottom up approach
      It is also termed as tabulation technique. In this, all subproblems are needed to be solved in advance and then used to build up a solution to the larger problem.
2. Optimal sub structure
   It implies that the optimal solution can be obtained from the optimal solution of its subproblem. So optimal substructure is simply an optimal selection among all the possible substructures that can help to select the best structure of the same kind to exist.

Comparison between feasible and optimal solution

1) Feasible solution

While solving a problem by using a greedy approach, the solution is obtained in a number of stages. The solution which satisfies the problem constraints they are called a feasible solution.

2) Optimal solution

Among all the feasible solution if the best solution either it can have a minimum or maximum value is chosen it is an optimal solution.