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.


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.