Steps of Dynamic Programming.

Steps of Dynamic Programming

1. Define Sub problems
   Break a problem into sub-problems.Usually this is the tough part, identifying sub problems is half job done.
   
2. Guess Part of solution.Guess a solution of the sub-problem and the trick is don't just try any guess, try them all.
   
3. Recurrence Relation.
   Most important step.Once you have identified the sub-problems, the recurrence relation will be trivial.
   
4. Recurse + MemoizeStep-4 and step-5 will follow once completed first 3 steps.
   
5. Solve original Problem
   Use solution to sub-problems to solve the original problem.

Running Time

Running Time = No. of Sub-problems . Time/sub-problem

Eg. 

consider worked out example for Edit Distance Problem.

Given two strings X and Y and set of operations replace (R), insert (I) and delete (D) all at equal cost. Find minimum number of edits (operations) required to convert one string into another.

Sub-problem:

==========

Suffix of X =>  X[i:]

Suffix of Y =>  Y[j:]

Considering length of X (|X|) = m and length of Y(|Y|) = n.

Total No. of Sub-problems = O(|X||Y|) = O(mn).

Guess

=====

From current position 3 decisions can be taken,

Replace X[i] -> Y[j] and advance both i and j.

Insert Y[j] and advance j.

Delete X[i] and advance i.

Recurrence

========

At current position select the minimum cost operation, out of all 3 operations.

DP(i,j) = min( REPLACE_COST(X[i],Y[j]) + DP(i+1,j+1) , INSERT_COST(Y[j]) + DP(i,j+1), COST_DELETE(X[i] ) + DP(i+1,j))

Solve Original Problem

================

DP(m,n) = Minimum cost.

Running Time 

=========

No. of Subproblems = O(mn)

Time/Subproblem = O(1).

Running Time = O(mn).