# matrix-chain multiplication problem

(classic problem)

**Definition:**
Given a sequence of matrices such that any *matrix* may be multiplied by the previous matrix, find the best association such that the result is obtained with the minimum number of arithmetic operations. One may use *dynamic programming* to find the best association.

Author: SKS

## More information

Dan Hirschberg's example of using dynamic programming for matrix multiplication, including pseudocode.

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with Paul Black.

Entry modified 17 December 2004.

HTML page formatted Fri Feb 23 10:06:08 2018.

Cite this as:

Sandeep Kumar Shukla, "matrix-chain multiplication problem", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/matrxchnmltp.html