Discrete Mathematics

--------------------------DESIGN

OF

ALGORITHMS

315

This is the essence

of

dynamic programming. Recognizing that during the course

of

problem solving,

sub-problems are repeating too many times, one can keep a look-up table

of

the sub-problems. Whoever

begins

to

compute a sub-problem records an entry in that table and before embarking on expanding a tree

node, check in the table to see

if

someone has already done that job.

We have seen a similar situation with a much simpler situation earlier: the

Fibonacci series. The

definition for this series is:

fib(n) =

fib(n-

1) +

.fib(n-

2).

However, no one computes the series this way, why? Consider ...