資料結構與演算法

(5 points) We want to multiply a sequence of matrices $M_1, \dots, M_n$ with the minimum number of multiplications. Since the matrix multiplication is associative, we can parenthesize the matrix multiplication in all possible orders. Let $m_{i,j}$ be the minimum number of multiplications to multiply $M_i, \dots, M_j$. We can derive a recursion of $m_{i,j}$, where $r_i$ and $c_i$ are the numbers of rows and columns of the matrix $M_i$ respectively.

m_{i,j} = \min_{i \le k < j} \left( m_{i,k} + m_{k+1,j} + r_i c_k c_j \right) \tag{1}

Now consider $m_{s,s+k}$, $1 < s < s+k < n$. For given $s$ and $k$, let $x$ be the number of $m_{i,j}$'s that have $m_{s,s+k}$ at the right-hand side of Equation 1, and let $y$ be the number of different $m$'s that are at the right-hand side of Equation 1 when $i = s$ and $j = s+k$. What is the approximate value of $x + y$?