From Introduction to Algorithms by CLRS:

15.2-4 Describe the subproblem graph for matrix-chain multiplication with an input chain of length n. How many vertices does it have? How many edges does it have, and which edges are they?

I've figured out everything except for the number of edges. I've looked at several solutions but I am having trouble understanding even those. The best solution I've found so far is this one. I understand that every vertex has two outgoing edges for every $k$ such that $i\le k\le j-1$. One edge for $A[i...k]$ and one edge for $A[k+1...j]$. It also makes sense why we need to sum over all the vertices. What confuses me is this statement in the solution:

...each value $j-1=k$ can be obtained for precisely $n-k$ different pairs $1\le i\le j\le n$ (vertices).

I think the equation $j-1=k$ is a mistake and should be $j-i=k$ instead but I'm not certain. Can someone explain (in baby steps) why each value of $k$ is obtained for $n-k$ vertices?


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.