How to do this : Scan the chain from left to right in pairs of matrices and find the least cost (minimum scalar multiplications) for multiplication. Now parenthesize the pair and calculate its size and total cost. Continue this process until all matrices are included. Cost of multiplying two matrices of size $p$x$q$ and $q$x$r$ is $pqr$ and the size of the resultant matrix is $p$x$r$.
Given matrices $F_1,F_2,F_3,F_4,F_5$ of sizes $2$x$25, 25$x$3, 3$x$16, 16$x$1$ and $1$x$1000$ respectively.
Step 1 : Compute cost of $F_1F_2\Rightarrow2$x$25$x$3$ $= 150$
$F_2F_3 \Rightarrow 25$x$3$x$16 = 1200$
$F_3F_4 \Rightarrow 3$x$16$x$1 = 48$
$F_4F_5\Rightarrow 16$x$1$x$1000 = 16000$
The $least$ cost is for $F_3F_4$, so make it paranthesized. Now size of $(F_3F_4)$ is $3$x$1$ and cost is $48$.
Step 2: Repeat the process with paranthesized pair and its size from above step.
Now matrices are : $F_1F_2(F_3F_4)F_5$
Cost of $F_1F_2 = 150$ (as above)
$F_2(F_3F_4) \Rightarrow 25$x$3$x$1 = 75$
$(F_3F_4)F_5 \Rightarrow 3$x$1$x$1000 = 3000$
The least here is $75$, so parenthesize $(F_2(F_3F_4))$. Its size is now $25$x$1$ and total cost now is $48+75$.
Step 3: Now matrices are : $F_1(F_2(F_3F_4))F_5$. Scan again from left to right in pairs.
Cost of $F_1(F_2(F_3F_4)) \Rightarrow 2$x$25$x$1 = 50$
Cost of $(F_2(F_3F_4))F_5 \Rightarrow 25$x$1$x$1000 = 25000$
Least is $50$ for $(F_1(F_2(F_3F_4))$ and its size becomes $2$x$1$. Total cost is $48+75+50$
Step 4: Now only one pair is there, $(F_1(F_2(F_3F_4)))F_5$, and its cost is $2$x$1$x$1000 = 2000$.
So the required paranthesization for minimum cost is $(F_1(F_2(F_3F_4)))F5$ and the total cost is $48+75+50+2000 = 2173$.
