Matrix Chain Multiplication

Matrix Chain Multiplication. Given matricies $A_0,\dots ,A_{n-1}$ with dimensions $(m_0\times m_1),(m_1\times m_2),\dots ,(m_{n-1}\times m_n)$, which order should we multiply the matricies in order to minimize the number of scalar multiplications? Description from course

Idea:

• Search every subproblem but with Dynamic Programming.
• for every chain of matricies, get the split with minimum multiplication required.
• Iterate for increasing gap (=chain length)