Editing Matrix chain multiplication (section)

== A dynamic programming algorithm ==

To begin, let us assume that all we really want to know is the minimum cost, or minimum number of arithmetic operations needed to multiply out the matrices. If we are only multiplying two matrices, there is only one way to multiply them, so the minimum cost is the cost of doing this. In general, we can find the minimum cost using the following [[recursion|recursive algorithm]]:

* Take the sequence of matrices and separate it into two subsequences.
* Find the minimum cost of multiplying out each subsequence.
* Add these costs together, and add in the cost of multiplying the two result matrices.
* Do this for each possible position at which the sequence of matrices can be split, and take the minimum over all of them.

For example, if we have four matrices ''ABCD'', we compute the cost required to find each of (''A'')(''BCD''), (''AB'')(''CD''), and (''ABC'')(''D''), making recursive calls to find the minimum cost to compute ''ABC'', ''AB'', ''CD'', and ''BCD''. We then choose the best one. Better still, this yields not only the minimum cost, but also demonstrates the best way of doing the multiplication: group it the way that yields the lowest total cost, and do the same for each factor.

However, this algorithm has exponential runtime complexity making it as inefficient as the naive approach of trying all permutations. The reason is that the algorithm does a lot of redundant work. For example, above we made a recursive call to find the best cost for computing both ''ABC'' and ''AB''. But finding the best cost for computing ABC also requires finding the best cost for ''AB''. As the recursion grows deeper, more and more of this type of unnecessary repetition occurs.

One simple solution is called [[memoization]]: each time we compute the minimum cost needed to multiply out a specific subsequence, we save it. If we are ever asked to compute it again, we simply give the saved answer, and do not recompute it. Since there are about ''n''<sup>2</sup>/2 different subsequences, where ''n'' is the number of matrices, the space required to do this is reasonable. It can be shown that this simple trick brings the runtime down to O(''n''<sup>3</sup>) from O(2<sup>''n''</sup>), which is more than efficient enough for real applications. This is [[Top-down and bottom-up design|top-down]] dynamic programming.

The following bottom-up approach<ref name="Cormen">
{{cite book
  | last1 = Cormen
  | first1 =  Thomas H
  | author-link1 = Thomas H. Cormen
  | last2=Leiserson
  | first2=Charles E
  | author-link2 = Charles E. Leiserson
  | last3=Rivest
  | first3=Ronald L
  | author-link3 = Ron Rivest
  | last4=Stein
  | first4=Clifford
  | author-link4 = Clifford Stein
  | title = Introduction to Algorithms
  | volume = Second Edition
  | chapter = 15.2: Matrix-chain multiplication
  | pages = 331–338
  | publisher = MIT Press and McGraw-Hill
  | year = 2001
  | isbn = 978-0-262-03293-3
}}
</ref> computes, for each 2 ≤ ''k'' ≤ n, the minimum costs of all subsequences of length ''k'' using the costs of smaller subsequences already computed.
It has the same asymptotic runtime and requires no recursion.

Pseudocode:
<syntaxhighlight lang="java">
// Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
MatrixChainOrder(int dims[])
{
    // length[dims] = n + 1
    n = dims.length - 1;
    // m[i,j] = Minimum number of scalar multiplications (i.e., cost)
    // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
    // The cost is zero when multiplying one matrix
    for (i = 1; i <= n; i++)
        m[i, i] = 0;

    for (len = 2; len <= n; len++) { // Subsequence lengths
        for (i = 1; i <= n - len + 1; i++) {
            j = i + len - 1;
            m[i, j] = MAXINT;
            for (k = i; k <= j - 1; k++) {
                cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];
                if (cost < m[i, j]) {
                    m[i, j] = cost;
                    s[i, j] = k; // Index of the subsequence split that achieved minimal cost
                }
            }
        }
    }
}
</syntaxhighlight>
* Note: The first index for dims is 0 and the first index for {{var|m}} and {{var|s}} is 1.

A [[Python (programming language)|Python]] implementation using the memoization decorator from the standard library:

<syntaxhighlight lang="python3">
from functools import cache

def matrix_chain_order(dims: list[int]) -> int:
    @cache
    def a(i, j):
        return min((a(i, k) + dims[i] * dims[k] * dims[j] + a(k, j) 
                   for k in range(i + 1, j)), default=0)

    return a(0, len(dims) - 1)
</syntaxhighlight>