title: Matrix Chain Multiplication Dynamic Programming
body: <p>Assume that multiplying a matrix G1 of dimension p×q with another matrix G2 of dimension q×r requires pqr scalar multiplications. Computing the product of n matrices G1G2G3 ….. Gn can be done by parenthesizing in different ways. Define GiGi+1 as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain G1G2G3G4G5G6 using parenthesization (G1(G2G3))(G4(G5G6)), G2G3 and G5G6 are only explicitly computed pairs.</p>
  
  <p>Consider a matrix multiplication chain F1F2F3F4F5, where matrices F1,F2,F3,F4 and F5 are of dimensions 2×25,25×3,3×16,16×1 and 1×1000, respectively. In the parenthesization of F1F2F3F4F5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are</p>
  
  <p>F1F2 and F3F4 only</p>
  
  <p>F2F3 only</p>
  
  <p>F3F4 only</p>
  
  <p>F2F3 and F4F5 only</p>
  
  <p>=======================================================================</p>
  
  <p><em>My approach - I want to solve this under one minute, but the only way I know is that to use Bottom up Dynamic Approach by making a table and the other thing I can conclude is we should multiply with F5 at last because it has 1000 in it's dimension.So, please how to develop fast intuition for this kind of question!</em></p>
  
  <p>======================================================================</p>
  
  <p><strong>Correct answer is F3F4</strong></p>