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
Spatial reasoning: for example, solving 3D drawing problems.
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 fib n
Recurrence solution
fib n
1
when n < 2
fib(n-1) + fib(n-2) otherwise
fib 5 calls fib 4 fib 3
fib 4 calls fib 3 fib 2
fib 3 calls fib 2 fib 1
fib 2 calls fib 1 fib 0
Convert to table filling
Table F[] size n
F[0] = 1
F[1] = 1
for i = 2 to n
F[i] = F[i-1] + F[i-2]
return F[n]
Use memoised function
fibm n
for
i = 0 to n
if n < 2 return 1
if F[n] != 0 return
F[n]
else return fibm(n-1) +
fibm(n-2)
Code for fib (written in Som v1)
Optimal binary search tree
Code for bst
the output of the run shows the C table and the result.
d:\prabhas\6teach\algo\algo2005>somv1
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