Matrix Chain Multiplication using Dynamic Programming

hello friends today we are going to see the matrix chain multiplication problem this is a dynamic programming problem and in this problem we are going to find out the cost for multiplication of a chain of matrices so before going to the problem you have to first understand the rules of matrix multiplication and the method of how to find out the cost of matrix multiplication okay so let's see so the first rule is see for matrix multiplication number of columns in first matrix is equal to number of rows in second Matrix so let's see what it is here a is multiplied with B so a into B gives you this matrix okay now see the first row and the first column cell means 1 1 so this is the cell now this answer value comes by multiplying the first row of a with the first column of B so the first row of first matrix into the first column of second Matrix that is 1 1 now 1 2 this is the second column so 1 2 so this cell value comes by multiplying the first row of a with second column of B ok so this is the 1 then 1 3 this value comes by multiplying the first row of a with the third column of B and 1 for this value comes by multiplying the first row with the 4th column of B so that means if we multiply the second row of a with the first column of B it will give us this value that is 2 1 then 2 2 2 3 respectively multiplying the second column third column and fourth column of B so as you can observe here for the value of one one means for this value we have multiplied the first row with the first column of B so when we multiply you can see here AP AP plus bu plus CT bu plus CP means we multiply each element in that row with each element in the column right that means for multiplication the number of elements in this row should be equal to the number of elements in this column means the number of elements in the row of a should be equal to the number of elements in the column of B okay so obviously you can see here number of elements means the number of columns number of elements in a row means the number of columns because as the number of columns is three here that's why the number of elements is equal to three in this row so that is n means number of columns in first matrix is equal to the number of elements in the first column means the number of rows see the number of elements in a column is equal to the number of rows here in this column there are three elements that means there are three rows in this matrix okay now so that is the here I will write that is and for the second matrix now this is the number of columns in first matrix is equal to the number of rows in second Matrix right so that is the first rule then only multiplication can take place now the second rule see Oh M cross n matrix multiplied with n cross K gives you a matrix with dimension M cross K M cross K okay C means the answer matrix will be M cross K okay you can see it here see we have multiplied this to my dresses and we have got this M cross K matrix means 3 cross 4 matrix okay 3 rows and 4 columns right now the third rule how to find out the cost C so for finding out the cost you have to find out the number of multiplications taking list so C for one sale for one sale how many multiplications take place three multiplications here what is the meaning of three multiplications it is equal to n see it is equal to n n multiplications take place for one sale because there are n elements in the row of first matrix multiplying with the n elements in the column of second Matrix ok so that's why n multiplications take place for one sale and how many such cells are there M cross K cells are there so for each cell n multiplications take place so M cross K cross n these are the number of multiplications taking place so I have written it here M cross n cross K I have written it in this way because it will be easy to understand like this if M cross n matrix multiplies with n cross K matrix then see M cross the common n into K this is the cost M cross the common n cross K this is the cost now as we have understood the rules for matrix multiplication let's go and solve the problem so if you have been given five mattresses that is a 0 a 1 a 2 a 3 and a 4 and these are the sizes of those mattresses so a 0 matrix is of size 3 cross 4 then a 1 is of size 4 cross 5 that is M cross n okay and similarly for a 2 a 3 and a 4 the sizes are 5 cross 6 6 cross 2 and 2 cross 5 respectively so here I have mentioned 2 ways to multiply these matrices so see suppose the first way is first we multiply a 0 and a 1 then 2 the result of that multiplication we multiply a 2 then 2 this result we multiply a 3 and again we multiply a 4 so let's start the multiplication so first a 0 into a 1 means 3 by 4 into 4 by 5 so as you know we say this as M by n into n by K like mentioned here seen M by n into n by K so what is the result matrix size that is M by K see 3 by 4 into 4 by 5 so the result will be 3 by 5 so that is the result here 3 by 5 now what is this see this is the cost of multiplication like written here if we multiply M cross n with n cross K then the cost of multiplication is M into n into K right M into the common n into K so here the cost of multiplication will be M into n into K means 3 into 4 into 5 okay that is the cost now as the result size of multiplication a 0 into a 1 is 3 by 5 now we have to multiply a 2 to this result so I have taken a 2 here so what is the size of a 2 that is 5 by 6 so it is here what will be the cost of multiplication 3 into 5 into 6 and what is the result C 3 by 6 because M n and n K so the result will be M by K so that is here so 3 by 6 and the cost is 3 into 5 into 6 again a 3 comes here to multiply the result of this multiplication so the result is this so 3 by 6 into 6 by 2 so the cost will be 3 into 6 into 2 and the result will be 3 by 2 so it is written here again let's multiply that result by a 4 so 3 by 2 into 2 by 5 so the cost will be 3 into 2 into 5 and the result will be 3 by 5 ok so let's calculate the total cost C 3 into 4 into 5 is 60 3 into 5 into 6 is 90 3 into 6 into 2 is 36 and 3 into 2 into 5 is 30 so let's add them ok so 60 plus 90 is 150 plus 36 is 186 plus 30 so that is equal to 216 so there are total 216 multiplications taking place when we multiply these five matrices in this way okay now let's see the another way so suppose you multiply a 0 and a 1 first parallely you multiply a 2 and a 3 then you multiply their results with each other and then to this result you multiply a 4 ok so let's see how it is done C is 0 into AZ into a 1 means 3 by 4 into 4 by 5 so the cost is 3 into 4 into 5 and the result is 3 by 5 now a 2 into 8 3 means 5 by 6 into 6 by 2 so the cost is 5 into 6 into 2 and the result will be 5 by 2 see this is a 0 into a 1 and this is a 2 into a 3 now you have to multiply these 2 right so 3 by 5 into 5 by 2 so the cost is 3 into 5 into 2 and the result will be 3 by 2 okay now this is 3 by 2 is the result now this result should be multiplied with a 4 right so 3 by 2 into 2 by 5 so the cost will be 3 into 2 into 5 and the result will be 3 by 5 here okay so let's see what is a total cost so 3 into 4 into 5 so it is 60 and here 5 into 6 into 2 this is also 60 okay then 3 into 5 into 2 this is 30 and 3 into 2 into 5 this is also 30 so what is the total see 60 plus 60 is 120 plus 30 is 150 plus 30 is 180 so 180 is the total cost ok so see here the cost of multiplication in this way and in this way are different see but the answer of multiplication will be same means the answer matrix of this whole multiplication whatever will be the resultant matrix that answer will be same for both processes only because we multiply them in a different way the cost will be different similar to the multiplication operation of numbers like a 2 B 2 C even if you multiply B into C first and then you multiply a or you multiply a to be first and then you multiply with C the answer will be same so same is the case here the result will be same but in case of matrix multiplication the cost will be different okay and we have to find out the minimum cost and that way in which the cost is minimum so there is a possibility that some other way make you a cost which is less than 180 okay so that way we'll be efficient our problem statement is to find out the minimum cost of a matrix chain multiplication and we are going to use dynamic programming now to find out that minimum cost so for dynamic programming we always start from smaller subproblems and then we go towards the bigger subproblems so here see first we have to solve for L equal to zero means there are zero multiplications that means there is only an individual matrix C this is the base condition for our memoization matrix then L equal to one that means there is one multiplication which in another word means a group of two matrices okay means if there are two matrices then there will be one multiplication then we will go for L equal to 2 that means a group of three matrices okay and similarly we go up to L equal to four means a group of five matrices that is our final size okay so when L is equal to 0 that means the individual matrix so I represents the starting of the group and J represents the ending of the group if that is an individual matrix obviously starting is 0 ending is 0 for the first cell means a 0 see if there is no multiplication then the cost will be you know then I equal to 1 J equal to 1 this sale okay for the individual matrix so 1 1 means a 1 ok and again the cost will be 0 because there is only one matrix we have considered that is a 1 then there is no multiplication so the cost is 0 to 2 that is a 2 means the cost is 0 3 3 that is a 3 cost is 0 and similarly 4 4 4 that is a 4 and the cost is 0 now let's go to L equal to 1 means a group of 2 matrices see we are going to fill in a diagonal way these are the diagonals ok just remember we are going to feel the values in a diagonal way now 0 1 C 0 1 means a 0 a 1 ok means a group of 2 now if there is a group of 2 then we have only one possibility that is multiplying those two matrices we can only multiply in one way that is a 0 into a 1 so here 0 a 1 means 3 into 4 into 5 so what is the cost 3 into 4 is 12 12 into 5 is 60 so 60 is the cost now another group of 2 is a 1 a 2 okay means a 1 a 2 so 4 into 5 into 6 so 4 into 5 is 20 20 into 6 is 120 so 120 is the cost now the third group is a 2 a 3 okay so a 2 a 3 see here 5 into 6 is 30 30 into 2 is 60 and the last group is a 3 a 4 so a 3 a 4 means 6 into 2 is 12 12 into 5 is 60 yes we have calculated the cost for L equal to one means a group of size two now let's go to a group of size three means L equal to two okay so what is the first group of size three that is a 0 a 1 and a 2 means I is 0 and J is 2 so 0 2 means this is the cell 0 and 2 so this is the same now here is the twist for a group of size 3 means if it is a 0 a 1 and a 2 we cannot directly write the cost of multiplying these three because there are two possibilities to multiply a 0 a 1 and a 2 and I have written the possibilities here now let's see see the first possibility is that we keep a 0 as it is and we multiply a 1 a 2 okay and after we multiply a 1 a 2 we multiply a 0 to the result of a 1 a 2 and the second possibility is that first you multiply a 0 a 1 and then you multiply a 2 to the result okay so these are the two ways in which we can multiply a 0 a 1 and a 2 right so for the group of size 3 means for L equal to 2 as we know there are 3 cases means for a group of size 3 there are 3 groups means a 0 a 1 a 2 a 1 a 2 a 3 and a 2 a 3 a 4 inside one group inside this group there are two possibilities similarly inside this group also there are 2 possibilities and inside this group there are 2 possibilities now let's first concentrate on this group how to find out the cost of those two possibilities as you can here see first I have separated a zero and I have written a 1 and a 2 in the bracket after that I have written a 0 a 1 in the bracket and I have separated it means there is a partition point see what I'm saying there is a partition point and that partition point is K that is K okay so what is that key so this is the formula right this is the formula for that partition and finding out the cost of the partition see M of I J means here I is equal to 0 and J is equal to 2 for a 0 a 1 a 2 I is 0 and J is 2 he is equal to M of I K because K is the partition point from where we are dividing the group that is the partition point so for K is equal to 0 here see M of I is 0 and K is 0 means M of 0 0 so let's see in the matrix this is the matrix M M of 0 0 that means a 0 ok so a 0 is separated ok plus C this is the cost for a 0 plus M of k plus 1 2 J as K is 0 0 plus 1 is 1 and J is 2 okay J is 2 so M of 1 2 means 1 2 means this same which tells us the cost for a 1 a 2 ok so that is here a 1 8 means the first partition contains only a zero and the second partition contains a 1 a 2 okay in this way we found out our first partition so that is here see a zero and the second partition is a 180 if you want you can you bracket to a zero also means this is one partition this is second partition now how to find out the cost see we know the cost we have memorized the cost for zero zero zero zero and that cost is zero okay so for a zero the cost is zero plus for a 1 a 2 also we have memorized the cost that is what the dynamic programming is all about we are memorizing the values means when we are going for L equal to two we are making use of the values for L equal to 1 and L equal to 0 we are using these values which we have memorized inside this memorization table so 1 2 so what is the value for 1 2 that is 120 means it is 120 here so 0 plus 120 now the third part in the formula is this and I will explain this formula here now see what is the dimension of a 0 it is 3 by 4 and what is the dimension of a 1 and a 2 it is 4 by 5 and 5 by 6 so see here as this is an individual matrix we don't need to solve now a 1 a 2 so here if we solve this you can see 4 by 5 into 5 by 6 the result dimension will be 4 by 6 now as both brackets are solved now the results are here for the two brackets now a final model application has to be performed between these two matrices of size 3 by 4 and 4 by 6 so here is the extra cost means here is this extra cost for the multiplication of these results what I mean to say is that we have already memorized the minimum cost for these two problems see 0 0 is 0 and 1 2 is 120 okay 1 2 is 120 so we don't solve these problems we directly concentrate on the results here 3 by 4 and 4 by 6 see this result 3 by 4 & 4 by 6 this dimension is not given to us or we have not memorized this dimension okay so how will we find out the final cost of the multiplication of these two matrices we have only memorized the costs we have not memorized the dimensions okay so we have to find out some way of figuring out those dimensions to multiply just for finding out that extra cost this cost so now as 3 is p0 we can say that p0 is the first dimension of first partition because see P I and I is 0 okay and J is 2 here so as I is 0 okay that means that is the first matrix in the first partition okay so you can say that it is p0 means it is P I which is which is written here okay now the second p1 means PK plus 1 what is k k is 0 k is 0 okay and PK plus 1 is P 1 so that is 4 yes so 4 is P 1 so we can say that it is first dimension in second partition see in the second partition what are the dimensions 4 5 that is common and 6 means P 1 P 2 and P 3 so what is P 1 C it is the first dimension in the second partition this is the second partition and P 1 is the first dimension in this second partition out of P 1 P 2 and P 3 that is what I have written here okay and P 3 is the last dimension in this second partition P 3 is the last dimension in second partition so 3 into 4 into 6 so 3 4 z 12 12 6 are 72 so that means 120 plus 72 so that is equal to 192 is the total now then k equal to 1 so what is the meaning of k equal to 1 means the partition is the first matrix means a 0 a 1 will come in one partition and the remaining a 2 will go in another partition that is k equal to 1 this is the partition point okay now for this let's start 0 to 1 0 to 1 that is 16 cost of a0 a1 is 60 cost of 2 means 2 2 that is individual so that is 0 and finally plus TI into PK plus 1 into AJ plus 1 so see now what is the partition that is a 0 into a 1 is the first partition and a 2 is the second audition so P I means the first dimension that is 3 ok that is p 0 then P k plus 1 means the first dimension in the second partition so what is the first dimension in the second partition that is P 2 that is fine okay so that is PK plus 1 and P J plus 1 is the last dimension in the group what is the last dimension that is 6 3 into 5 into 6 means 90 to 90 plus 60 is 150 so 150 is the total cost for k equal to 1 now what is minimum obviously which method we will prefer we will prefer the second method for k equal to 1 means we will multiply in this way okay so 150 is the cost for this method so let's write it here for 0 to 2 150 is the cost and one more important point here see for calculating 150 what is the partition point that partition point is K is equal to 1 okay so you have to store k equal to 1 here this helps us to know how is the partition for this group for 0 to 2 what is the partition point you have to memorize that partition point so that when you go in reverse you can understand in what way we have multiplied these matrices you can find out that arrangement of matrices okay and now this formula see M of IJ is equal to 0 if i equal to j see if i is equal to j then obviously that is 0 but if i is not equal to j then it is minimum of see here what we did we took the minimum the is written in this formula minimum of whatever is the partition point CK ranges from I to J means if I is zero and J is to K was having two values C zero and one zero comma one so it ranges from zero to two K is less than J means K cannot be two so the last matrix cannot be the partition point it will only go from zero to two means it will take values 0 and 1 and we will take minimum of those two partition point costs this is the same thing as you have seen here only extra thing written here is we are going to take minimum cost of all the partition points that is written in this formula this is our final formula for every cell this formula works for every cell now here I tell you why I have not filled values in these cells see why no values in these cells because I is less than J in our formula but here C 1 is greater than 0 C is greater than 0 so I have not filled the values because we are not capable of multiplying the matrices in rivers see if you go for 1 0 1 0 means what a 1 a 0 so can you multiply 4 5 & 3 4 means a 1 is 0 4 5 and 3/4 C number of columns should be equal to the number of rows as you have studied the condition for matrix multiplication but they are not equal here so for all eyes which are greater than J you cannot fill the values because these cells do not satisfy the condition of matrix multiplication okay let's go ahead so the second case is a 1 a 2 a 3 means I equal to 1 J equal to 3 so the second group is a1 a2 a3 so here if partition point is 1 means a1 will be separate and a2 a3 okay now what is the cost for a 1 means 1 1 that cost is zero okay plus the cost for a2 a3 means 2 3 so that cost is 60 okay plus the multiplication of the results that is the cost for multiplication is VI into PK plus 1 into PJ plus 1 means the first dimension of the first partition that is 4 this is the first dimension then the first dimension of the second partition is 5 4 into 5 into the last dimension that is 2 okay so C 4 into 5 is 20 20 into 2 is 40 so 40 plus 60 is 100 okay so 100 is the cost for this partitioning method now if k equal to 2 then what will be the partition C a1 a2 and a3 so this is the partition for k equal to 2 because the second Matrix is the partition point so let's do it here a 1 a 2 and a 3 okay so what is the cost for a 1 a 2 see here 1 2 so that cost is 120 okay plus what is the cost for a 3 C 3 3 so that cost is 0 plus C the multiplication of the results the cost for that multiplication is here C P 1 that is the first dimension of the first partition so P 1 that is for into what is the second partition a3 is the second partition what is the first dimension of second partition that is six into the last dimension in this group or you can say the last dimension of the second partition so that is 2 so 4 into 6 into 2 so let's add so 120 plus 4 into 6 is 24 into 2 is 48 so that is 120 plus 48 is 168 okay so what is minimum see hundred is minimum means k equal to 1 so this partition is giving us the minimum cost so we write hundred as the minimum cost for one two three and k equal to one is the partition now let's go for the third case that is a 2 a 3 and a 4 see for L equal to 2 these are the three cases and now we are at the third case that is a 2 a 3 and a 4 so the first thing is the partition point is to see the partition point ranges from i to j as it is a 2 2 a 4 so i is 2 and J is 4 so k will take values 2 & 3 okay so the first value is 2 so what will be the partition for k equal to 2 see here for a 2 a 3 a 4 if K is equal to 2 means this is one partition and a 3 a 4 is another partition okay so what will be the cost for that for the partition a 2 and a 3 a 4 as the second position okay now what is the cost for a to see here 4 8 2 2 so that is 0 plus a 3 a 4 so what is 4 3 4 that is 16 so 60 is the cost plus this factor so you know now how to calculate this see the first dimension of the first partition is our P I that is p2 so it is 5 into the first dimension in the second partition that is 6 and the last dimension in the second partition that is fine okay so let's add them 5 into 6 is 30 into 5 is 150 150 plus 60 is 200 and then let's go for partition point k equal to 3 so that partition is a 2 a 3 and then a 4 ok as 3 is the partition point from a2 to a3 there will be one politician and a 4 will be an another partition now 2 2 3 what is the cost 2 2 3 that is 16 plus 4 that is 0 plus C for a2 to a3 is 1 partition and a4 is another partition so what is the first dimension in the first partition that is fine you do what is the first dimension in the second partition that is 2 into what is the last dimension in the second partition this is 5 so 5 into 2 into 5 so 5 into 2 is 10 into 5 is 50 so 50 plus 60 is 110 okay so what is minimum 110 is minimum so I write here 110 for 2 to 4 and K is equal to 3 right yes so this is over 4 l is equal to 2 means a group of size 3 right now we will make use of these three values means these values for the group of one two and three and we will calculate value for the group of four now for L equal to three so let's go for L equal to three now now for L equal to three the first group is a 0 a 1 a 2 a 3 so here it is a 0 a 1 a 2 and a 3 and the second group is a 1 a 2 a 3 a 4 which is written here see a 1 a 2 a 3 and a 4 so these are the two groups for L equal to 3 means the group of size 4 now for the first group suppose the partition point is 0 means K is equal to 0 so two partitions will be a 0 and a 1 a 2 a 3 so these are the two partitions now let's calculate the cost c400 the cost is 0 plus a 1 2 a 3 means 1 2 3 so that is 100 the cost is hundred plus this factor so see what is the first partition first partition is a 0 and the second partition is a 1 a 2 a 3 so these are the two partitions so the first dimension in the first partition is 3 into the first dimension in the second partition is 4 into the last dimension in the second partition is 2 okay so 0 plus 100 plus 3 into 4 is well 12 into 2 is 24 so the total is 124 ok now let's go for partition k equal to 1 now if k equal to 1 is the partition means a 1 is the partition point so a 0 a 1 in one group and a 2 a 3 in another group right now what is is a one cost C zero to 1 means 60 is the cost plus what is a2 a3 cost a2 a3 so again that cost is also 60 Plus this factor so a0 a1 and a2 a3 are the two partitions so a0 a1 and a2 a3 so what is the first dimension in the first partition that is 3 which is P I then what is the first dimension in the second partition here it is fine that is PK plus 1 and what is the last dimension in the second partition that is - that is PJ plus 1 so in 2 so 60 plus 60 is 120 plus 3 into 5 is 15 into 2 is 13 so 120 plus 30 is 150 right now see here if we take k equal to 2 as the partition point see here there are 3 partition points because I is 0 and J is 3 so K ranges from 0 to 3 means K will take values 0 1 and 2 ok because K is less than 3 so values will be 0 1 and 2 so now the partition point 2 so for k equal to 2 the partitions are see here a 0 a 1 a 2 and a 3 is the last partition ok so now what is the cost for 0 to 2 0 to 2 the cost is 115 plus what is the cost for a 3 that is an individual matrix so the cost is zero plus see these are the two partitions a 0 2 8 2 is 1 partition and a 3 is another partition so the first time a in the first partition is three which is P I into the first dimension in the last partition is 6 which is PK plus 1 into the last dimension in the second partition is 2 so that is 2 which is PJ plus 1 so 3 into 6 into 2 okay so 3 into 6 is 18 into 2 is 36 plus 150 so the total cost is 186 right so what is minimum 124 150 and 186 so 124 is minimum means k equal to 0 is the optimal partition point so 124 is the cost for 4 0 to 3 means a 0 to a 3 for that group for this group and k equal to 0 is the partition point ok so now let's go for the second group for L equal to 3 the second group is a 1 a 2 a 3 and a 4 now if k equal to 1 is the partition point what will be the partition see the partition will be from a 1 to a 1 and now a 2 2 a 4 will be the second partition for k equal to 1 C a1 and a2 a3 a4 so what is the cost for a1 that is an individual matrix so 0 plus 2 2 4 2 2 4 so that is 100 and then plus C first dimension of the first partition is 4 into first dimension of the second partition is 5 into the last dimension of second partition is 5 4 into 5 into 5 so 4 into 5 is 20 20 into 5 is hundred 100 plus 110 is 210 so 210 is the total cost now for k equal to 2 what will be the partition see a 1 a 2 and a 3 a 4 these are the two partitions okay now see for 1 to 2 120 is the cost plus 4 3 2 4 60 is the cost okay plus see what are the two partitions a 1 a 2 and a 3 a 4 so the first dimension of the first partition is 4 into the first dimension of the second partition is 6 into the last time mention of the second partition is 5 120 plus 60 is 180 plus C 4 into 6 is 20 4 into 5 is 120 so 180 plus 120 so that is equal to 300 now for k equal to 3 let's see what are the partitions C a1 a2 a3 and a4 okay now what is the cost for a1 to a3 a1 to a3 that is hundred so hundred is the cost plus for a 4 0 will be the cost because that is an individual matrix now plus C what is the dividend a1 to a3 and a4 first dimension of the first partition that is 4 then first dimension of second partition that is 2 and last dimension of second partition that is 5 so see 100 plus 4 into 2 is 8 8 into 5 is 40 so 140 140 is the total cost for k equal to 3 means out of 210 300 and 140 what is minimum 140 is the minimum so k equal to 3 is the partition point and for 1 2 4 means for a-1 a 4c 140 is the cost and k equal to 3 is the partition point now let's go to the final cell that is 0 2 4 means all the mattresses ok so let's see 4 0 2 4 so for L equal to 5 I is 0 and J is 4 okay so the first partition point is 0 it will go from 0 to 4 means now k will take values 0 1 2 and 3 okay now for k equal to 0 what will be the partition C a0 is 1 partition and the second partition is a1 a2 a3 and a4 okay let's calculate the cost for a 0 0 is the cost for a1 to a4 1 2 4 that is 1 40 is the cost plus this factor so that is C what is the partition a 0 is 1 partition and a1 a2 a3 4 is the second partition so the first dimension of the first partition is 3 into the first dimension of the second partition is 4 into the last dimension of the second partition that is 5 okay so 3 into 4 into 5 so 3 into 4 is 12 12 into 5 is 16 140 plus 60 is 200 is the total cost now for k equal to 1 C a0 a1 is 1 partition and a2 a3 a4 is second position okay because 1 is the partition point a 0 and a 1 will be the 1 partition and from k plus 1 means from a2 to a4 is the second partition now for zero to 160 is the cost plus a2 to a4 - for 110 is the cost-plus now see you have to calculate the cost for multiplication of the results of these two subproblems so what are the subproblems a 0 to a 1 this is the first partition and a 2 a 3 a 4 is the second partition so first dimension of the first partition is 3 first dimension of the second partition is fine into the last dimension of the second partition is fine okay so 3 into 5 is 15 into 5 is 75 75 plus 110 is 185 185 plus 60 is 240 fine okay now let's go for k equal to 2 so the partition is a 0 a 1 a 2 and a 3 a 4 okay now from 0 to 2 150 is the cost plus 3 to 4 3 to 4 60 is the cost plus C 0 to 2 is 1 partition for this and 3 to 4 is another partition so first dimension of the first partition is 3 into first dimension of second partition is 6 into last dimension of the second partition is 5 so 3 into 6 is 18 18 into 5 is 90 90 plus 60 is 150 150 plus 150 is 300 is the cost for k equal to 2 now for k equal to 3 let's see C a0 a1 a2 a3 and a4 is the second partition so 4 0 2 3 0 2 3 1 24 is the cost then plus 4 a 4 C 0 is the cost Plus now see what is the partition a0 to a3 and a4 is the second partition okay now first dimension of the first partition that is 3 into first dimension of second partition that is 2 into last dimension of second partition that is 5 okay so 3 into 2 into 5 so 3 into 2 is 6 6 into 5 is 30 so 30 plus 124 is 154 so what is minimum 154 is minimum means k equal to 3 is the partition point and 154 is the minimum cost so here I write 154 and k equal to 3 as the partition point okay so the minimum cost for multiplication of 0 2 for the matricis a 0 a 1 a 2 a 3 and a 4 is 154 now how to trace back means how to find out that arrangement of matrices that arrangement of brackets so let's see that so see this is very simple you have to start at the end means the last cell in which we got the cost for 0 to 4 okay now 154 is the cost and partition point is 3 means for these four matrices the partition point is 3 so get the partition done okay now now you have to see in this bracket there cannot be further partition now what will be the partition in this bracket okay for 0 to 3 C 4 0 to 3 here 124 is the minimum cost but partition is k equal to 0 so for k equal to 0 let's make the partition see a 0 is one partition and a 1 a 2 another partition okay inside this partition this is the partition so I will write it again here C a0 a1 a2 a3 this is one and a four okay now inside check there can be partition in a1 to a3 so 1 2 3 what is the partition k equal to 1 is the partition that means that means C a1 is 1 partition and a2 a3 is another politician right now now there cannot be further partition so I will write it here C a0 into a1 into a2 a3 this is 1 and to the wall you multiply with a 4 okay so that is the partition and this that is the arrangement of brackets hey friends please subscribe to my channel as I post algorithm videos every day and if you want a video on any particular topic then please mention in the comment below thank you

Channel: Vivekanand Khyade - Algorithm Every Day

Views: 26,055

Keywords: Matrix Chain Multiplication using Dynamic Programming, Matrix column equal to rows, Dynamic Programming, find minimum cost of multiplication of the chain of matrices, data structure, computer science, algorithm, programming, placement, interview, question, code

Id: ASsN8qNHFXI

Length: 56min 13sec (3373 seconds)

Published: Thu Sep 21 2017