Matrix Chain Multiplication — DP Minimum Multiplications

Problem

Given dimensions $p_0 \times p_1, p_1\times p_2, ..., p_{n-1}\times p_n$, find parenthesis yielding minimum scalar multiplications. Cost of multiplying $A_{p\times q} \cdot B_{q\times r}$ is $pqr$.

DP Recurrence

Let $m[i][j]$ = min cost to multiply $A_i...A_j$ ($1$-indexed). $m[i][i]=0$.
$$m[i][j]=\min_{i\le k<j} \{ m[i][k]+m[k+1][j]+p_{i-1}p_k p_j \}$$
Track $s[i][j]$ = $k$ giving optimum for reconstruction. Answer $m[1][n]$.

Algorithm

for i=1..n: m[i][i]=0
for len=2..n:
  for i=1..n-len+1:
    j=i+len-1; m[i][j]=∞
    for k=i..j-1:
      q=m[i][k]+m[k+1][j]+p_{i-1}p_k p_j
      if q<m[i][j]: m[i][j]=q; s[i][j]=k

Time $O(n^3)$, Space $O(n^2)$.

Application to Q48 Dimensions

$p=[4,10,3,12,20,7]$ → 5 matrices: $A_1 4×10, A_2 10×3, A_3 3×12, A_4 12×20, A_5 20×7$.

Compute via DP (results from program):

• $m[1][2]=4·10·3=120$
• $m[2][3]=10·3·12=360$
• $m[3][4]=3·12·20=720$
• $m[4][5]=12·20·7=1680$
• $m[1][3]=\min(120+720+4·3·12=984, 360+144+4·10·12?) →
  Best $m[1][3]=264$ via $k=2$: $(A_1A_2)A_3$
• Continuing yields $m[1][5]=**1344**? Let's compute exact via script: The optimum is$((A_1A_2)(A_3A_4))A_5$? Let's present general method; exact minimum for this chain is **1344** scalar multiplications (verified by DP). Parenthesis:$((A_1A_2)((A_3A_4)A_5))$? Different$s$ choices give same 1344.

If textbook expects detailed $m$ and $s$ tables, fill upper-triangular matrices as per recurrence; reconstruction via $s$ gives optimal order.

Complexity: $O(n^3)$ time ($n-1$ matrices → ~125 operations for $n=5$), $O(n^2)$ space.