Skip to main content
Logo image

Section C.11 A2: Dynamic Programming


  • 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.