資料結構與演算法(A) 國立臺灣大學 2022 第 16 題

(5 points) Dynamic programming can be used to solve the matrix-chain multiplication problem. Suppose we hope to compute the matrix product $A_1 A_2 \dots A_6$ with the matrix dimensions as follows.

matrix	$A_1$	$A_2$	$A_3$	$A_4$	$A_5$	$A_6$
dimension	$30\times35$	$35\times15$	$15\times5$	$5\times10$	$10\times20$	$20\times25$

Let $m[i, j]$ be the minimum number of scalar multiplications needed to compute the matrix $A_i A_{i+1} \dots A_j$ . What is $m[2, 5]$ ?

標準解析