1. DP on Sequence

(1) Simple Induction
Formula: f(i) = g(f(i-1), w(i))
Examples: Assembly-line Scheduling (CLRS), mean filter, …

(2) Sequential Division(# of divisions unknown)
Classic Problem: LDS
Formula: f(i)=optimize{f(k)+w(k+1,i)}
where f[i] is the optimum value for s[0..i]
Extension: Sort the sequence first and then do LDS. We may need to sort the sequence using multiple keywords and then do LDS on the last keyword in the cases where one keyword is equal..
Examples: Beautiful People (sgu199), segments (ural 1078), Printing Neatly(CLRS)

(3) Sequential Division(# of divisions known)
Formula: f(i,j)=optimize{f(k,j-1)+w(k+1,i)}
where f(i,j) is the optimal division of s[0..i] into j parts.
Examples: Integer Multiplaction(given n digits, add m multiplication signs to achieve maximum product)

(4) Hierachical Division
Formula: f(i,j)=optimize{f(i,k-1)+f(k+1,j)+w(i,j,k)}
where f(i,j) is the sum of weights associated with the optimal division of s[i..j].
Examples: Matrices Multiplication, Optimal Binary Search Tree, Triangulation of Simple Polygon

(5) Hierachical Division (on Looped Sequence)
Formula: f(i,j)=optimize{f(i,k)+f(t,j-k)+w(i,j,k)}
where t=(i+k)mod n. Let j’=(i+j)mod n, then f(i,j) is the sum of weights associated with the optimal division of s[i..j’] (i.e. j consecutive elements from s[i]). w[i,j,k] is the weight for dividing s[i..j’] at t.
Examples: Pebble Merging

(6) Matching Two Sequences
Classic Problem: LCS
Formula:
f(i,j) = optimize{ f(i-1, j-1) + w(i,j),
                           f(i   , j-1) + w(empty,j),
                           f(i-1, j   ) + w(i,empty)}
where f(i,j) is the best soultion for x[0..i] and y[0..j]. Pre-conditions may be associated with the tree terms to be optimized.
Examples: Little Shop of Flowers(sgu104), Editing Distance(CLRS)

2. DP on trees/graphs

No special formula. Use post-order DFS on trees and optimize over all children. DP for trees are typically in O(n).
Prim/Kruskal, Dijkstra are typical DP on graphs.

3. DP for NP problems

Basic Problems: 0-1 Knapsack, Weighted Scheduling, Scheduling to Maximum Profit(CLRS)
Formula: f(i,j)=optimize{f(i-1,j),f(i-1,j-c(i))+w(i)}
where f(i,j) is the optimum value for x[0..i] under the constraint of j resources, c(i) is the cost of i, w(i) is the gained weight of i.
Tips: You only have two choice for each i, pick it or leave it there.