Answer is **C.**

Ordering:

- First Multiply $M_2 \times M_3.$

This requires $100*20*5$ multiplications.
- Then Multiply $M_1 \times (M_2 \times M_3).$

This requires $10*100*5$ multiplications.
- Then Multiply $(M_1 \times (M_2 \times M_3)) \times M_4.$

This requires $10*5*8$ multiplications.

Total $19000$ Multiplications.

**Brute Force approach **- anyone can do.

No. of possible ordering for 4 matrices is $C_3$ where $C_3$ is the $3^{rd}$ Catalan number and given by $n=3$ in $\frac{1}{n+1} {}^{2n}C_n = 5.$

So, here we have

- $(M_1 \times M_2) \times (M_3 \times M_4)$
- $(M_1 \times (M_2 \times M_3)) \times M_4$
- $((M_1 \times M_2) \times M_3) \times M_4$
- $M_1 \times (M_2 \times (M_3 \times M_4))$
- $M_1 \times ((M_2 \times M_3) \times M_4))$

Each of these would give no. of multiplications required as

- $pqr + rst + prt $
- $qrs + pqs + pst$
- $pqr + prs + pst$
- $rst + qrt + pqt$
- $qrs + qst + pst$

The last 2 are having $qt$ terms which are the highest terms by far and hence we can avoid them from consideration $qt = 8000$ multiplied by one other term would be larger than any value in choice. So, just find the value of first 3 terms.

- $pqr + rst + prt = 20000 + 8000 + 16000 = 44000$
- $qrs + pqs + pst = 10000 + 5000 + 4000 = 19000$ - smallest value in choice, we can stop here.
- $pqr + prs + pst$

**Dynamic Programming Solution **(should know Matrix Chain Ordering algorithm)

Here we have a chain of length 4.

Dynamic programming solution of Matrix chain ordering has the solution

$m[i, j] = \begin{cases} 0 &\text{ if } i=j\\ \min_{i\leq k < j } m[i]k] + m[k+1][j] + p_{i-1}p_{j}p_{k} &\text{ if } i < j\end{cases}$

So, we can fill the following table starting with the diagonals and moving upward diagonally. Here $k < j$ but $\geq i.$

$$\begin{array}{|l|l|l|l|l|} \hline \text{} & \textbf{j=1} & \textbf{j=2} & \textbf{j=3} & \textbf{j=4}\\\hline

\textbf{i=1} & \text{0} & \text{$p_0p_1p_2$} & \min(10000+p_0p_1p_3, & \min(18000+ p_0p_1p_4, \\

&&=20000&20000+p_0+p_2p_3)&20000+8000+p_0+p_2+p_4, \\

&&&=15000&15000+p_0p_3p_4) = 19000

\\\hline

\textbf{i=2} & \text{} & \text{0} & \text{$p_1p_2p_3 = 10000$} & \text{$\min(10000 + p_2p_3p_4), p_1p_3p_4)$}\\

&&&&=18000

\\\hline

\textbf{i=3} &\text{} & \text{} & \text{0} &\text{$p_2p_3p_4 = 8000$} \\\hline \textbf{i=4} &\text{} &\text{} & \text{} & \text{0} \\\hline \end{array}$$

Our required answer is given by $m[1,4] = 19000.$