Dynamic Programming


Suitable for the problem that has overlapped substructures
The final solution is assembled from solutions of subproblems
The solutions of subproblem are reused.
Type of problem:   optimisation problems

Reused

temporal
spatial

Step of designing DP

Analyse and write recurence solutions
Converting from recurrence to fill tables.  The order of filling the table is the key.
Alternative is to use temporal ordering:  Use memoised function.

Memoised function

remember the answer that has already been calculated.  This is why the subsolution can be reused.

Example fibonacci number

Fibonacci  numbers are  0, 1, 1, 2, 3, 5, 8, 13, ...

Recurrence solution

fib n =
  0                       when n = 0
  1                       when n < 2
  fib(n-1) + fib(n-2)     otherwise

  naive implementation causes exponential number of call to fib(.)

Convert to table filling  (use spatial)

Table F[]  size n + 1

F[0] = 0
F[1] = 1
for i = 2 to n
   F[i] = F[i-1] + F[i-2]
return F[n]

Use memoised function  (use temporal)

// assume F[.] = 0 initially

F[0] = 0
F[1] = 1
fibm n
if n == 0  return F[0]
if F[n] != 0  return F[n]
else
  F[n] = fibm(n-1) + fibm(n-2)
return F[n]

Code for fib   (written in Som)

Optimal binary search tree

Code for bst 

the output of the run shows the C table and the result.

d:\prabhas\6teach\algo\algo2007>som3 bst.txt
215

22 58 102 117 183 189 215
0 18 56 66 121 127 153
0 0 20 30 80 84 102
0 0 0 5 35 39 57
0 0 0 0 25 29 47
0 0 0 0 0 2 12
0 0 0 0 0 0 8

215

Interval scheduling

Demo-interval-scheduling

Tools

The above examples are written in Som language  (see my page)  here is the executable package

last update 29 June 2007