\documentclass[11pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{booktabs}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,decorations.pathreplacing}
\usepackage{hyperref}
\hypersetup{colorlinks=true,linkcolor=blue!50!black,urlcolor=blue!50!black}

% ---- theorem-like environments ----
\theoremstyle{plain}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}
\theoremstyle{definition}
\newtheorem{remark}{Note}

% ---- shortcuts ----
\newcommand{\DP}{\mathrm{DP}}

% ---- colors ----
\definecolor{leftc}{RGB}{38,131,131}    % teal: the "left" piece A_i..A_k
\definecolor{rightc}{RGB}{214,124,40}   % orange: the "right" piece A_{k+1}..A_j

% ---- code style ----
\lstset{
  basicstyle=\ttfamily\small, breaklines=true, columns=fullflexible,
  keepspaces=true, showstringspaces=false,
  commentstyle=\color{green!45!black}, keywordstyle=\color{blue!60!black},
  language=Python, frame=single, framesep=4pt, rulecolor=\color{black!25}, xleftmargin=2pt,
}

\title{\textbf{Matrix-Chain Multiplication}\\[2pt]
\large Dynamic Programming Lecture Notes (CS5800)}
\author{Virgil Pavlu\\[2pt]\normalsize\itshape notes written by Claude}
\date{}

\begin{document}
\maketitle
\vspace{-2em}

%==================================================================
\section*{The problem, and why the order matters}
%==================================================================

We are given a chain of $n$ matrices $A_1,A_2,\dots,A_n$ to multiply together. Matrix $A_t$
has dimension $p_{t-1}\times p_t$, so consecutive dimensions match and the product
$A_1A_2\cdots A_n$ is defined. Matrix multiplication is \emph{associative} --- every way of
parenthesizing gives the same matrix --- but the \emph{cost} (number of scalar
multiplications) depends heavily on \emph{how} we parenthesize. Multiplying a $p\times q$ by
a $q\times r$ matrix costs $p\,q\,r$ scalar multiplications. \textbf{We want the
parenthesization that minimizes the total scalar multiplications.}

\paragraph{A tiny example.} Take $A_1\,(10\times100)$, $A_2\,(100\times5)$,
$A_3\,(5\times50)$.
\[
  (A_1A_2)A_3:\ \underbrace{10\cdot100\cdot5}_{5000}+\underbrace{10\cdot5\cdot50}_{2500}=7500,
  \qquad
  A_1(A_2A_3):\ \underbrace{100\cdot5\cdot50}_{25000}+\underbrace{10\cdot100\cdot50}_{50000}=75000.
\]
Same answer matrix, but one order is \emph{ten times} cheaper. With $n$ matrices the choice
matters a lot.

\paragraph{Why not just try them all?} Let $P(n)$ be the number of full parenthesizations of
$n$ matrices. Splitting at the top level between matrix $k$ and $k+1$ gives
$P(n)=\sum_{k=1}^{n-1}P(k)\,P(n-k)$ with $P(1)=1$ --- the Catalan recurrence. A quick
induction gives $P(n)\ge 2^{n-2}$, and in fact $P(n)=\Omega(4^n/n^{3/2})$. Exhaustive search
is hopeless; but the same ``split at the top'' idea, \emph{memoized}, is exactly the DP.

\paragraph{Running example.} We carry the classic $n=6$ instance through the document:
\[
  (p_0,p_1,\dots,p_6)=(30,\,35,\,15,\,5,\,10,\,20,\,25),
\]
so $A_1\!:\!30\!\times\!35$, $A_2\!:\!35\!\times\!15$, $A_3\!:\!15\!\times\!5$,
$A_4\!:\!5\!\times\!10$, $A_5\!:\!10\!\times\!20$, $A_6\!:\!20\!\times\!25$.

\bigskip
\noindent The DP is built in five steps. We mark each one explicitly.

%==================================================================
\section*{Step 1 --- Solution characterization (divide \& conquer)}
%==================================================================

\emph{Goal of this step: show that an optimal parenthesization is built from optimal
parenthesizations of two sub-chains.}

Any parenthesization of $A_i A_{i+1}\cdots A_j$ (with $i<j$) makes \emph{one} multiplication
last: the outermost product splits the chain between some $A_k$ and $A_{k+1}$, $i\le k<j$,
\[
  \bigl(\underbrace{A_i\cdots A_k}_{\text{left}}\bigr)\bigl(\underbrace{A_{k+1}\cdots A_j}_{\text{right}}\bigr).
\]

\begin{claim}[Optimal substructure]\label{cl:sub}
If a parenthesization of $A_i\cdots A_j$ is optimal and its top-level split is at $k$, then
the way it parenthesizes the left sub-chain $A_i\cdots A_k$ is itself optimal for that
sub-chain, and likewise for the right sub-chain $A_{k+1}\cdots A_j$.
\end{claim}

\begin{proof}
Cut-and-paste. The total cost is $(\text{cost of left})+(\text{cost of right})+
p_{i-1}p_k p_j$, where the last term is the price of the single final multiply (a
$p_{i-1}\times p_k$ matrix times a $p_k\times p_j$ matrix) and does \emph{not} depend on how
the two halves are internally parenthesized. So if some cheaper parenthesization of the left
sub-chain existed, swapping it in would lower the total --- contradicting optimality. Same
for the right.
\end{proof}

\noindent So an optimal solution for $A_i\cdots A_j$ is built from optimal solutions of two
strictly shorter sub-chains. That is the divide-and-conquer shape DP needs --- the only
thing we don't know yet is \emph{where} to split.

%==================================================================
\section*{Step 2A --- The DP recurrence}
%==================================================================

Define the table in English first:
\[
  \DP[i][j]\;=\;\text{the minimum number of scalar multiplications to compute }A_i A_{i+1}\cdots A_j .
\]
A single matrix costs nothing, so $\DP[i][i]=0$. For $i<j$ we don't know the top-level split
$k$, so by Claim~\ref{cl:sub} we \emph{try them all} and keep the cheapest:
\[
\boxed{\;
  \DP[i][j]=
  \begin{cases}
     0 & i=j,\\[4pt]
     \displaystyle\min_{\,i\le k<j}\Bigl(\,\DP[i][k]+\DP[k+1][j]+p_{i-1}\,p_k\,p_j\,\Bigr) & i<j.
  \end{cases}
\;}
\]
We also store $S[i][j]=\arg\min_k$, the split that achieved the minimum --- needed to
reconstruct the parenthesization in Step~4. The answer is $\DP[1][n]$.

\paragraph{Worked entry.} On the running example, $\DP[2][5]$ (the chain $A_2A_3A_4A_5$):
\[
\DP[2][5]=\min
\begin{cases}
k{=}2:\ \DP[2][2]+\DP[3][5]+p_1p_2p_5 = 0+2500+35\cdot15\cdot20 = 13000,\\
k{=}3:\ \DP[2][3]+\DP[4][5]+p_1p_3p_5 = 2625+1000+35\cdot5\cdot20 = \mathbf{7125},\\
k{=}4:\ \DP[2][4]+\DP[5][5]+p_1p_4p_5 = 4375+0+35\cdot10\cdot20 = 11375,
\end{cases}
\]
so $\DP[2][5]=7125$ with best split $S[2][5]=3$.

%==================================================================
\section*{Step 2B --- Subproblem dependence and the fill order}
%==================================================================

\emph{Goal of this step: lay the subproblems out and see which ones each cell needs, so we
know a safe order to fill the table bottom-up.}

A subproblem is an interval $[i,j]$ of the chain, so we index the table by its two
endpoints: the \textbf{first index $i$} on the horizontal axis, the \textbf{second index
$j$} on the vertical axis. Only cells with $i\le j$ exist (an interval can't run backwards),
so the table is the \emph{upper-left triangle}; the main diagonal $i=j$ holds the base cases
$\DP[i][i]=0$. The full problem is the far corner $\DP[1][n]$.

\begin{center}
\begin{tikzpicture}[>=Stealth, font=\small,
   cell/.style={circle, draw=black!55, fill=white, inner sep=1.1pt},
   base/.style={circle, fill=gray!55, inner sep=1.3pt},
   act/.style={circle, fill=red!75!black, inner sep=2.2pt}]
% unused region (i>j)
\fill[black!5] (1.5,0.5)--(8.5,0.5)--(8.5,7.5)--cycle;
% axes
\draw[->] (0.2,0.5)--(9.3,0.5) node[below right]{\footnotesize first index $i$};
\draw[->] (0.5,0.2)--(0.5,9.3) node[left]{\footnotesize second index $j$};
% diagonal (base cases)
\draw[gray!45] (0.8,0.8)--(8.4,8.4);
\foreach \d in {1,...,8}{\node[base] at (\d,\d) {};}
\node[anchor=west,font=\footnotesize,gray] at (8.3,8.4) {$\DP[i][i]{=}0$ (base)};
% the cell C[i,j] and the cells it reads
\node[act] (Cij) at (2,7) {};
\node[act] (Cik) at (2,4) {};
\node[act] (Ckj) at (5,7) {};
\foreach \yy in {3,5,6} {\node[cell] at (2,\yy) {};}
\foreach \xx in {3,4,6} {\node[cell] at (\xx,7) {};}
% labels for the three active cells
\node[anchor=south,font=\footnotesize] at (2,7.2) {$\DP[i][j]$};
\node[anchor=north,font=\footnotesize] at (2,3.8) {$\DP[i][k]$};
\node[anchor=south,font=\footnotesize] at (5,7.2) {$\DP[k{+}1][j]$};
% red arrows for one split k
\draw[->,thick,leftc]  (Cij)--(Cik) node[pos=0.5,right=1pt,font=\scriptsize]{left $A_i\!\dots\!A_k$};
\draw[->,thick,rightc] (Cij)--(Ckj) node[pos=0.5,below=2pt,font=\scriptsize]{right $A_{k+1}\!\dots\!A_j$};
% full problem corner
\node[act] (full) at (1,8) {};
\node[anchor=south west,font=\footnotesize,red!70!black] at (0.7,8.1) {$\DP[1][n]$};
% region + fill-order (in the free lower-right)
\node[font=\footnotesize,gray] at (5.3,2.2) {unused: $i>j$};
\draw[->,gray!55,line width=1.6pt] (8.2,2.5)--(6.5,4.2);
\node[gray!60,font=\footnotesize,align=center] at (7.7,1.5) {fill by chain\\ length $\ell=j{-}i{+}1$};
% axis ticks
\foreach \x/\lab in {1/$1$, 2/$i$, 5/$k{+}1$, 7/$j$, 8/$n$} {\draw (\x,0.42)--(\x,0.58); \node[anchor=north,font=\footnotesize] at (\x,0.4){\lab};}
\foreach \y/\lab in {2/$i$, 4/$k$, 7/$j$, 8/$n$} {\draw (0.42,\y)--(0.58,\y); \node[anchor=east,font=\footnotesize] at (0.4,\y){\lab};}
\end{tikzpicture}
\end{center}

\noindent To compute $\DP[i][j]$ the recurrence pairs, for each split $k$, one cell
\emph{straight down its column} ($\DP[i][k]$, same $i$, lower $j$) with one cell
\emph{straight right along its row} ($\DP[k{+}1][j]$, same $j$, larger $i$). As $k$ runs from
$i$ to $j-1$, those two markers slide toward the diagonal, sweeping the whole column-below
and row-right. Every cell it reads is strictly \emph{closer to the diagonal} --- i.e.\ has a
\emph{shorter} chain. So the safe \textbf{bottom-up order is by increasing chain length}
$\ell=j-i+1$: first the diagonal ($\ell=1$, all $0$), then $\ell=2$, and so on, each diagonal
using only shorter ones already computed, until the lone corner $\DP[1][n]$ ($\ell=n$). This
diagonal order is the one genuinely non-obvious thing about matrix chain --- you cannot just
sweep rows or columns.

%==================================================================
\section*{Step 3 --- Bottom-up pseudocode}
%==================================================================

\begin{lstlisting}
MATRIX-CHAIN-ORDER(p, n):       # p = (p0, p1, ..., pn);  A_t is p[t-1] x p[t]
    for i in 1..n:
        DP[i][i] = 0                          # base: a single matrix costs 0
    for L in 2..n:                            # L = chain length, increasing
        for i in 1..(n-L+1):
            j = i + L - 1
            DP[i][j] = +infinity
            for k in i..(j-1):                # try every top-level split
                q = DP[i][k] + DP[k+1][j] + p[i-1]*p[k]*p[j]
                if q < DP[i][j]:
                    DP[i][j] = q
                    S[i][j]  = k              # remember the best split
    return DP, S
\end{lstlisting}

\begin{remark}[Memoization here helps with \emph{order}, not with skipping]
Computing $\DP[1][n]$ needs \emph{every} interval $[i,j]$ --- all $\Theta(n^2)$ of them --- so
top-down memoization skips no subproblems; it is the same $\Theta(n^3)$ work. What it
\emph{does} buy is freedom from the diagonal bookkeeping: a recursive
\texttt{MEMO-CHAIN(i,j)} that returns $\DP[i][j]$, recursing on $(i,k)$ and $(k{+}1,j)$ and
caching, evaluates shorter chains first \emph{automatically}, so you never have to write the
``\texttt{for L}'' loop. (Contrast knapsack, where the natural order is trivial.)
\end{remark}

%==================================================================
\section*{Step 4 --- Tracing the optimal parenthesization}
%==================================================================

$\DP[1][n]$ is the optimal \emph{cost}; the actual parenthesization is read from $S$. Since
$S[i][j]$ is the top-level split, recurse: parenthesize $A_i\cdots A_{S[i][j]}$, then
$A_{S[i][j]+1}\cdots A_j$, wrapped in one pair of parentheses.

\begin{lstlisting}
PRINT-PARENS(S, i, j):
    if i == j:
        print "A" + i                         # a single matrix
    else:
        print "("
        PRINT-PARENS(S, i, S[i][j])            # left sub-chain
        PRINT-PARENS(S, S[i][j] + 1, j)        # right sub-chain
        print ")"
\end{lstlisting}

\paragraph{Filled table on the running example} ($n=6$), same axes as Step~2B: first index
$i$ along the bottom, second index $j$ up the side, the answer $\DP[1][6]$ in the top-left
corner. The diagonal is the base; shaded cells are the sub-chains used by the optimal
parenthesization.

\begin{center}
\begin{tikzpicture}[scale=1.0, font=\scriptsize]
% unused (i>j) lower-right cells
\foreach \i in {1,...,6}{\foreach \j in {1,...,6}{\ifnum\i>\j \fill[black!6] (\i-1,\j-1) rectangle (\i,\j);\fi}}
% base diagonal
\foreach \i in {1,...,6}{\fill[gray!16] (\i-1,\i-1) rectangle (\i,\i);}
% optimal-tree composite cells
\foreach \i/\j in {1/6,1/3,4/6,2/3,4/5}{\fill[leftc!16] (\i-1,\j-1) rectangle (\i,\j);}
\draw[help lines] (0,0) grid (6,6);
% values  (i = column, j = row);  cell (i,j) center at (i-0.5, j-0.5)
\foreach \i/\j/\v in {%
 1/1/0, 1/2/15750, 1/3/7875, 1/4/9375, 1/5/11875, 1/6/15125,
 2/2/0, 2/3/2625, 2/4/4375, 2/5/7125, 2/6/10500,
 3/3/0, 3/4/750, 3/5/2500, 3/6/5375,
 4/4/0, 4/5/1000, 4/6/3500,
 5/5/0, 5/6/5000,
 6/6/0}
 {\node at (\i-0.5,\j-0.5) {\v};}
% headers
\foreach \i in {1,...,6}{\node[font=\scriptsize] at (\i-0.5,-0.32){$i{=}\i$};}
\foreach \j in {1,...,6}{\node[anchor=east,font=\scriptsize] at (-0.12,\j-0.5){$j{=}\j$};}
\node[font=\footnotesize] at (3,-0.85){first index $i$};
\node[font=\footnotesize,rotate=90] at (-0.95,3){second index $j$};
\end{tikzpicture}
\end{center}

\noindent \textbf{Reconstruction from $S$.} The relevant splits are
$S[1][6]=3,\ S[1][3]=1,\ S[4][6]=5$:
\[
  \underbrace{S[1][6]=3}_{(A_1A_2A_3)(A_4A_5A_6)}\;\Rightarrow\;
  \underbrace{S[1][3]=1}_{A_1(A_2A_3)}\quad\text{and}\quad
  \underbrace{S[4][6]=5}_{(A_4A_5)A_6}.
\]
So the optimal parenthesization is $\bigl(A_1(A_2A_3)\bigr)\bigl((A_4A_5)A_6\bigr)$, at cost
$\DP[1][6]=15125$ scalar multiplications (versus $30\cdot35\cdot15\cdots$ far more for a naive
left-to-right product).

%==================================================================
\section*{Step 5 --- Running time and memory}
%==================================================================

\begin{center}
\begin{tabular}{ll}
\toprule
phase & cost\\
\midrule
number of cells (intervals $i\le j$)            & $\Theta(n^2)$\\
work per cell (the $\min$ over splits $k$)       & $O(n)$\\
filling the table                                & $\Theta(n^3)$ time\\
the $\DP$ and $S$ tables                          & $\Theta(n^2)$ space\\
\texttt{PRINT-PARENS}                             & $\Theta(n)$ time\\
\midrule
\textbf{total} & $\boldsymbol{\Theta(n^3)}$ time, $\boldsymbol{\Theta(n^2)}$ space\\
\bottomrule
\end{tabular}
\end{center}

\noindent The $\Theta(n^3)$ is tight: one can show the work is also $\Omega(n^3)$ (the inner
$\min$ over $k$ really does $\Theta(j-i)$ work, and summing over all intervals gives
$\Theta(n^3)$).

\paragraph{Can we do better?} Yes --- the \textbf{Hu--Shing} algorithm solves matrix-chain
ordering in $O(n\log n)$ by turning it into an optimal polygon-triangulation problem. Note
this is \emph{not} Knuth's $O(n^2)$ speedup: Knuth's trick needs the added weight to depend
only on the interval endpoints, but here the extra term $p_{i-1}p_k p_j$ depends on the split
$k$ itself. Its sibling, \textbf{Optimal BST}, has the same interval-DP shape \emph{and} a
split-independent weight, so there Knuth's monotonicity does give $O(n^2)$. For a first
course, $\Theta(n^3)$ is the algorithm to know.

\end{document}
