Matrix Chain Multiplication and Polygon Triangulation Revisited and Generalized

Thong Le, Dan Gusfield

The {\it matrix-chain multiplication} problem is a classic problem that is widely taught to illustrate dynamic programming. The textbook solution runs in $\theta (n^3)$ time. However, th…