Idea of dynamic
programming
programming
•Re-use
expensive computations
–Identify critical input to problem (e.g. best alignment of
prefixes of strings)
–Store
results in table, indexed by critical input
–Solve
cells in table of other cells
•Top-down
often easier to program
Albert Q.
Dynamic
at Whisler
mountain
Picture from PhotoDisc.com