Dynamic Programming

 Dynamic programming is a method for solving complex problems in maths and computer science in which large problems are broken down into smaller problems.

Through solving the individual smaller problems, the solution to the larger problem is discovered.

Stage – division of sequence of a system into various sub parts is called stages
State – a specific measurable condition of the system
Recursive equation – at every stage in dynamic programming the decision rule is determined by evaluating an objective function called recursive equation

Principle of optimality – it states that an optimal set of decisions rules has the property that regardless of the i^th decisions, the remaining decisions must be optimal with respect to the outcome that results from the i^th decision. This means that optimal immediate decision depends only on current state and not how you got there

The two basic approaches for solving dynamic programming are

• Backward recursion
• Forward recursion 

Backward Recursion

• It is a schematic representation of a problem involving a sequence of n decisions
• Then dynamic programming decomposes the problem into a set of n stages of analysis, each stage corresponding to one of the decisions. each stage of analysis is described by a set of elements decision, input state, output state and returns.

Forward Recursion 

• This approach takes a problem decomposed into a sequence of n stages and analyzes the problem starting with the first stage in the sequence, working forward to the last stage it is also known as deterministic probability approach

Advantages

• the process of breaking down a complex problem into a series of interrelated sub problems often provides insight into the nature of problem
• Because dynamic programming is an approach to optimization rather than a technique it has flexibility that allows application to other types of mathematical programming problems
• The computational procedure in dynamic programming allows for a built in form of sensitivity analysis based on state variables and on variables represented by stages
• Dynamic programming achieves computational savings over complete enumeration.

Disadvantages

• more expertise is required in solving dynamic programming problem then using other methods
• lack of general algorithm like the simplex method. It restricts computer codes necessary for inexpensive and widespread use

Video