Now if we multiply five matrices A1,A2,A3,A4,A5 then we will have to calculate the sequence in which minimum number of multiplications will have to be performed. Number of multiplications will have to be calculated as explained above. We can write above sequence A1,A2,A3,A4,A5 as (matrices 1 to k) x (matrices k+1 to n) i.e. if k=3 then (A1*A2*A3)(A3*A5) Now in (A1*A2*A3) again we will have to find the sequence in which minimum number of multiplications can be performed. Similarly in (A3*A5) we will have to find the sequence in which minimum number of multiplications will be performed. Also note that multiplying (A1*A2*A3) will result into one matrix and similarly multiplying (A3*A5) will result into one matrix. We will have to multiply both of these resultant matrices as well to get final result. So, overall Recurrence will be: Here m[i,k] represents the minimum operations performed by multiplying matrices from i to k. Similarly m[k+1,j] represents multiplying matrices k+1 to j. And pi-1*pk*pj represents number of multiplications required by multiplying resultant two matrices. m[i,i]=0 because it represents multiplying a single matrix in which case number of multiplications will be zero. In our case suppose i=1 and j=5 min[1,5] will be: ) Now if we consider k=1 Then = Similarly if k= 2 then = And so on
Now if we multiply five matrices A1,A2,A3,A4,A5 then we will have to calculate the sequence in which minimum number of multiplications will have to be performed. Number of multiplications will have to be calculated as explained above. We can write above sequence A1,A2,A3,A4,A5 as (matrices 1 to k) x (matrices k+1 to n) i.e. if k=3 then (A1*A2*A3)(A3*A5) Now in (A1*A2*A3) again we will have to find the sequence in which minimum number of multiplications can be performed. Similarly in (A3*A5) we will have to find the sequence in which minimum number of multiplications will be performed. Also note that multiplying (A1*A2*A3) will result into one matrix and similarly multiplying (A3*A5) will result into one matrix. We will have to multiply both of these resultant matrices as well to get final result. So, overall Recurrence will be: Here m[i,k] represents the minimum operations performed by multiplying matrices from i to k. Similarly m[k+1,j] represents multiplying matrices k+1 to j. And pi-1*pk*pj represents number of multiplications required by multiplying resultant two matrices. m[i,i]=0 because it represents multiplying a single matrix in which case number of multiplications will be zero. In our case suppose i=1 and j=5 min[1,5] will be: ) Now if we consider k=1 Then = Similarly if k= 2 then = And so on