Dynamic programming is used for optimization problems, where the solution is the result of a series of decisions d1,d2,...dn. Every decision depends on the one taken before and it isn't uniquely determined.

For applying this method we need to make sure that the optimality principle is satisfied:

if d1,d2...dn is an optimum series of decisions which transforms the initials state s0 into a final state sn going through the intermediary states s1,s2...sn-1, then the series of decisions d2,...dn is optimum for turning the state s1 into the state sn.

After checking the optimality principle we need to write the recurrence relations and solve them. These relations are of two types:

- every decision di depends of the decisions di+1..dn; the method being applied here is forward and the order in which the decisions are taken in is dn, dn-1...d1

- every decision di depends if the decision d1...di-1; the method applied here is backward and the order the decisions are taken in is d1, d2, ...dn.

Example: The number o possibilities of giving n prices to m people so that everybody gets a price.

Solution: The answer to this problem is Sterling's number:

st[n,m]=st[n-1,m-1]+m*st[n-1,m]

The number of possibilities of giving the prices is the sum between the number of possibilities of giving n-1 prices to m-1 people (giving the extra price to the extra person) and m* the number of possibilities of giving n-1 prices to m people (the extra price can be given to each of the m people).