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