Four matrices $M_1$, $M_2$, $M_3$ and $M_4$ of dimensions $p \times q$, $q \times r$, $r \times s$ and $s \times t$ respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as $((M_1 \times M_2) \times (M_3 \times M_4))$, the total number of scalar multiplications is $pqr + rst + prt$. When multiplied as $(((M_1 \times M_2) \times M_3) \times M_4)$, the total number of scalar multiplications is $pqr + prs + pst$. If $p = 10$, $q = 100$, $r = 20$, $s = 5$, and $t = 80$, then the minimum number of scalar multiplications needed is

We use the dynamic programming algorithm for Matrix Chain Multiplication. Given dimensions array $d = [d_0, d_1, d_2, d_3, d_4] = [10, 100, 20, 5, 80]$:

• $M_1: 10 \times 100$

• $M_2: 100 \times 20$

• $M_3: 20 \times 5$

• $M_4: 5 \times 80$

Chain Length 2:

• $m[1, 2] = d_0 d_1 d_2 = 10 \times 100 \times 20 = 20000$

• $m[2, 3] = d_1 d_2 d_3 = 100 \times 20 \times 5 = 10000$

• $m[3, 4] = d_2 d_3 d_4 = 20 \times 5 \times 80 = 8000$

Chain Length 3:

• For $m[1, 3]$:

  • $k = 1$: $m[1, 1] + m[2, 3] + d_0 d_1 d_3 = 0 + 10000 + 10 \times 100 \times 5 = 15000$

  • $k = 2$: $m[1, 2] + m[3, 3] + d_0 d_2 d_3 = 20000 + 0 + 10 \times 20 \times 5 = 21000$

  • $\implies m[1, 3] = 15000$

• For $m[2, 4]$:

  • $k = 2$: $m[2, 2] + m[3, 4] + d_1 d_2 d_4 = 0 + 8000 + 100 \times 20 \times 80 = 168000$

  • $k = 3$: $m[2, 3] + m[4, 4] + d_1 d_3 d_4 = 10000 + 0 + 100 \times 5 \times 80 = 50000$

  • $\implies m[2, 4] = 50000$

Chain Length 4 ($m[1, 4]$):

• $k = 1$: $m[1, 1] + m[2, 4] + d_0 d_1 d_4 = 0 + 50000 + 10 \times 100 \times 80 = 130000$

• $k = 2$: $m[1, 2] + m[3, 4] + d_0 d_2 d_4 = 20000 + 8000 + 10 \times 20 \times 80 = 44000$

• $k = 3$: $m[1, 3] + m[4, 4] + d_0 d_3 d_4 = 15000 + 0 + 10 \times 5 \times 80 = 19000$

Thus, the minimum number of scalar multiplications is 19000, achieved by the parenthesization $((M_1 \times (M_2 \times M_3)) \times M_4)$.

Hence, the correct option is (C).