= Matrix-chain dynamic programming
{title2=$m[i,j]$}
Let $A_i$ have <matrix dimensions> $p_{i-1}\times p_i$, where $p_0,\ldots,p_n$ are positive <integers>. For $1\leq i\leq j\leq n$, define $m[i,j]$ as the minimum <scalar multiplication> cost of the contiguous <matrix product> $A_i\cdots A_j$. The endpoints $(i,j)$ of an <integer interval> identify a <dynamic programming state>. A single <matrix> needs no <matrix multiplication>, giving the <base case> $m[i,i]=0$. At the final <matrix multiplication>, split after $A_k$:
$$
m[i,j]=\min_{i\leq k<j}\bigl(m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\bigr),\qquad i<j.
$$
The two subproducts have <matrix dimensions> $p_{i-1}\times p_k$ and $p_k\times p_j$, regardless of their internal grouping. The <recurrence relation> adds their optimal costs and the final <scalar multiplication> cost.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 21: Dynamic Programming III>[6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff; Lecture 21: Dynamic Programming III, printed p. 2, Parenthesization: final split, recurrence and zero one-matrix base case; notes use half-open indices]{ref}
Why is this <optimal substructure>? For a chosen final split $k$, replacing either subproduct's grouping by a cheaper one leaves its <matrix dimensions> and exact <matrix product> unchanged, so it decreases the whole cost by the same amount. Therefore an optimal grouping can use optimal groupings on both sides. Conversely, each candidate in the <recurrence relation> joins two achievable groupings. <Mathematical induction> on $j-i+1$, starting with the single-<matrix> <base case>, proves that the minimum is achievable and no grouping is cheaper.
There are also <overlapping subproblems>: while evaluating the different final splits of $ABCD$, the cases $A(BCD)$ and $(ABC)D$ both request the cost of $BC$. <Recursion> without reuse recomputes this answer; <memoization> or a <dynamic programming> table stores it once. Fill the table by increasing length $j-i+1$, so both dependencies are ready. Record an attaining split $s[i,j]$ alongside each cost.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 21: Dynamic Programming III>[6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff; Lecture 21: Dynamic Programming III, printed p. 2, Parenthesization: increasing substring size, cubic time and parent pointers]{ref}
The <dynamic programming> table has $n(n+1)/2$ cost entries. For length $\ell$, there are $n-\ell+1$ entries and $\ell-1$ possible splits, so the exact number of candidate evaluations is
$$
\sum_{\ell=2}^{n}(n-\ell+1)(\ell-1)=\frac{n(n-1)(n+1)}{6}.
$$
Under the unit-cost assumption that <arithmetic operations>, comparisons and access to stored costs each take constant time, this gives <time complexity> $O(n^3)$ and <space complexity> $O(n^2)$, using <Big O notation>. These bounds concern choosing a grouping from the <matrix dimensions>; they exclude the subsequent <matrix multiplication> work. If the dimensions or costs require arbitrarily long <integers>, their arithmetic and storage costs must also be counted.
Back to article page
