Skip to main content

Section C.11 A2: Dynamic Programming

Synopsis.

  • Dynamic programming is a technique to solve optimization problems that have optimal substructure

  • It uses memoization/tabulation to solve problems with overlapping sub-problems more efficiently

  • Intro example is shortest path; demonstrate that longest simple paths doesn't have optimal sub-structure

  • Explain memoization by Fibonacci numbers or binomial numbers

  • Introduction edit distance as an optimization problem and go through example.

Sections Covered.

Subsection 5.4.1 or Subsection 5.4.2, Subsection 5.4.3