Edit distance and matrix chain multiplication (Fundamental algorithms, Spring 2023, Lecture 5)
Kent Quanrud · 87:25
This lecture shows how to turn a clearly correct but exponential recursive algorithm into a polynomial-time one by caching subproblem answers (dynamic programming), using edit distance on strings and matrix-chain mult...