Cut rod problem, longest common subsequence, matrix-chain multiplication, knapsack problem, optimal substructure.
Example of dynamic programming using the cut rod problem.
Screencast Suthers 24 min
Example of dynamic programming using steps and LCS.
Screencast Suthers 17 min
Example of dynamic programming using LCS.
Screencast Suthers 18 min
Summary of dynamic programming.
Rod cutting, matrix-chain multiplication, elements of DP, longest common subsequence, optimal BSTs
Textbook 55 pages
Knapsack problem, matrix chain product, optimal BSTs, shortest paths, time and space requirements
Textbook 14 pages
Derivations of dynamic programming
Notes
Apply dynamic programming principles again
Homework