Consider we need to solve the Matrix chain multiplication using dynamic programming for this problem :

enter image description here

The table for min. cost is shown below :

enter image description here

Edit : Reference https://www.radford.edu/~nokie/classes/360/dp-matrix-parens.html

The table for Optimal locations for parentheses:

enter image description here

I know how to construct these tables but I don't know how to extract the min. number of multiplications that will be achieved for multiplying these matrices from the min cost table and also I can't construct the overall places of the parenthesis that should be used to achieve this min. number of multiplications from the optimal location of parenthesis table ? So please someone mention the resultant min. number of multiplications for this solution of this problem with the final parenthesis locations that should be used to achieve this min. number. Many thanks.

  • $\begingroup$ This problem is covered in many standard references. Which ones have you consulted? If the one you read wasn't helpful, maybe keep looking at others. I'm not sure there's much point in us repeating material that's already widely available in standard resources. $\endgroup$ – D.W. Apr 19 at 22:26
  • $\begingroup$ @D.W. Please support me with a resource( if avaialble with you already) answering this problem as I have done many searches regarding the construction of the final solution but I didn't find any . $\endgroup$ – Joo Apr 19 at 23:23
  • $\begingroup$ Can you edit the question to show us in the question what resources you've already read? You've asked two questions. Surely some of them describe how to extract the minimum number of multiplications, even if they don't describe how to construct the placement of the parentheses. No? $\endgroup$ – D.W. Apr 19 at 23:29
  • $\begingroup$ @D.W. Done editing. $\endgroup$ – Joo Apr 19 at 23:39
  • 1
    $\begingroup$ OK, so you read one reference. Well, that wasn't a very good one. I suggest you keep looking; there are lots of better explanations, including explanations in multiple algorithms textbooks. I don't see much point in us repeating what's already widely available. $\endgroup$ – D.W. Apr 19 at 23:46

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.