Lecture 23: Dynamic Programming

This lecture introduces dynamic programming, and discusses the notions of optimal substructure and overlapping sub-problems. Topics covered: Dynamic programming, optimal path, overlapping subproblems, weighted edges, specifications, restrictions, efficiency, pseudo-polynomials.