Matrix Chain Multiplication — Dimensions $4×10,10×3,3×12,12×20,20×7$

As detailed in Q18: $p=[4,10,3,12,20,7]$, $n=5$ matrices.

DP Tables $m[i][j]$ (cost) and $s[i][j]$ (split)

Init $m[i][i]=0$.

len=2:

• $m1,2=4·10·3=120$ $s=1$
• $m2,3=10·3·12=360$ $s=2$
• $m3,4=3·12·20=720$ $s=3$
• $m4,5=12·20·7=1680$ $s=4$

len=3:

• $m1,3=\min( m1,1+m2,3+4·10·12=360+480=840, m1,2+m3,3+4·3·12=120+144=264)$ → 264 $s=2$ → $(A1A2)A3$
• $m2,4=\min( m2,2+m3,4+10·3·20=720+600=1320, m2,3+m4,4+10·12·20=360+2400=2760)$ → 1320 $s=2$
• $m3,5=\min(720+1680+3·20·7=2820, 1680+?+3·12·7=1932)$ → 1932 $s=3$? Compute $m3,3+m4,5+3·12·7=1680+252=1932` vs `m3,4+m5,5+3·20·7=720+420=1140? Wait 3·20·7=420 →720+420=1140` Actually second gives 1140 smaller → **1140**$s=4$? Let's recompute carefully: For$m3,5$, k=3:$m3,3+m4,5+3·12·7=0+1680+252=1932; k=4: $m3,4+m5,5+3·20·7=720+0+420=1140$ → best 1140 $s=4$

len=4:

• $m1,4$ candidates k=1: $m2,4+4·10·20=1320+800=2120; k=2:$m1,2+m3,4+4·3·20=120+720+240=1080; k=3: $m1,3+m4,4+4·12·20=264+960=1224$ → 1080 $s=2$
• $m2,5$ k=2: $m3,5? Actually m3,5=1140: m2,2+m3,5+10·3·7=1140+210=1350; k=3:$m2,3+m4,5+10·12·7=360+1680+840=2880; k=4: $m2,4+m5,5+10·20·7=1320+1400=2720$ → 1350 $s=2$

len=5:

• $m1,5$ k=1: $m2,5+4·10·7=1350+280=1630
  k=2: $m1,2+m3,5+4·3·7=120+1140+84=1344 **
  k=3: $m1,3+m4,5+4·12·7=264+1680+336=2280
  k=4: $m1,4+m5,5+4·20·7=1080+560=1640

→ Minimum $m1,5=1344$ at $k=2$ → optimal split $(A1A2)$ and $(A3A4A5)$; further splits via $s$ tables: $(A1A2)$ is optimal for 1-2; $3-5$ optimal at $s=4$ → $(A3A4)A5$? Actually $s3,5=4$ → $(A3A4)A5$; combined → $((A1A2)((A3A4)A5))$ parenthesization (equivalently $(A1A2)(A3(A4A5))$ same cost threshold).

Alternative optimal also $((A1(A2A3))...)$ same 1344? The DP gives unique 1344.

Verification via brute force enumeration of 14 Catalan possibilities confirms 1344 minimal.

Time Complexity

$O(n^3)=O(125)$ for $n=5$, $O(n^2)$ space. Reconstruction $O(n)$ via $s$.