Divide and Conquer Solution

Input:

Output:

A paranthesization of the input sequence resulting in minimum number of multiplications needed to multiply the n matrices.

• Subgoal: Ignore Structure of Output (order of parenthesization), focus on obtaining a numerical solution (minimum number of multiplications)
• Define M[i,j] = the minimum number of multiplications needed to compute

  

  for

• Subgoal is to obtain M[1,n].

e.g. For,

M[1,1]=0,M[1,2]=1200,M[1,5]=690