0
$\begingroup$

In CLRS (Intro to algorithms 3rd Edition) on page 362, it says eqn(1) : enter image description here Lets Assume that you are given the cost of matrix multiplication for $A_{i}..A_{j}$ is $C[i,j]$ .
$C[i,j]$ is the Number of scalar multiplications of $A_{i}..A_{j}$.
$C[i,j]$ is not necessarily the optimal Number of scalar multiplications but obtained from this paranthesisation.
i.e $C[i,j]$ is derived from => $(A_{i}(A_{i+1}(A_{i+2}\dots(A_{j-2}(A_{j-1}A_{j}))...)$
Given that $C[i,j]$ has been provided to us. Can $m[i,j]$ be reduced the equation below.

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

Note $C[i,j]$ could be any parenthesizations so far as we are consistent.
I truly appreciate any help.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.