Dynamic Programming Characteristic & Application of Dynamic Programming

 

Dynamic Programming Characteristic and Applications

Dynamic programming is a problem solving technique that like divide and conquer solves problem by dividing them into sub-problems. Dynamic programming is used when the sub-problems are not independent when they share the same subproblems.  

Dynamic programming solves each sub-problem once and stores the result in a table so that it can be rapidly retrieved if needed again.It is often used in optimization problems.A problem with many possible solutions for which we want to find an optimal solution.Dynamic programming is an approach developed to solve sequential or multi stage decision problems hence the name dynamic programming.

Dynamic programming can be thought of as being the reverse of recursion.Recursion is a top down mechanism take a problem split it up and solve the smaller problems that are created.Dynamic programming is a bottom up mechanism solve all possible small problems and then combine them to obtain solutions for bigger problems.

Characteristics of Dynamic programming problem

• The problem can be divided into stages with a decision required at each stage.For example in the shortest path problem they were defined by the structure of the graph.
• Each stage has a number of states associated with it.The states for the shortest path problem was the node reached.
• The decision at one stage transforms one state into a state in the next stage.The decision of where to go next defined where arrived in the next stage.
• There exists a recursive relationship that identifies the optimal decision for stage j given that stage j+1 has already has solved.
• The final stage must be solved by itself.         

Applications of Dynamic programming

• Knapsack Problem.
• Mathematical optimization problems.
• Shortest path problems.
• Matrix chain multiplication.
• Longest common sequence.
• Time sharing schedule user and jobs to maximize CPU usage.

Difference between Divide and Conquer and Dynamic Programming

Divide and conquer algorithms splits a problem into separate subproblems solve the subproblems and combine the results for a solution to the original problem.Example Quick sort,Merge sort.Divide and conquer algorithms can be thought of as top down algorithms.In divide and conquer sub problem are independent.

Dynamic programming splits a problem into subproblems some of which are common solves the subproblems and combines the result for a solution to the original problem.Example Longest common sub-sequence.Dynamic programming can be thought of as bottom up.In dynamic programming sub-problems are not independent.Dynamic programming is generally used for optimization problems.