Matrix Chain Multiplication | DP | Dynamic Programming Python implementation of Matrix Chain Multiplication . See the Cormen book for details of the following algorithm ; Matrix Ai has dimension p [ i - 1 ] x p [ i ] for i = 1. . n ; For simplicity of the program , one extra row and one extra column are allocated in m [ ] [ ] . 0 th row and 0 th column of m [ ] [ ] are not used ; cost is zero when multiplying one matrix . ; L is chain length . ; q = cost / scalar multiplications ; Driver code
import sys NEW_LINE def MatrixChainOrder ( p , n ) : NEW_LINE INDENT m = [ [ 0 for x in range ( n ) ] for x in range ( n ) ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT m [ i ] [ i ] = 0 NEW_LINE DEDENT for L in range ( 2 , n ) : NEW_LINE INDENT for i in range ( 1 , n - L + 1 ) : NEW_LINE INDENT j = i + L - 1 NEW_LINE m [ i ] [ j ] = sys . maxint NEW_LINE for k in range ( i , j ) : NEW_LINE INDENT q = m [ i ] [ k ] + m [ k + 1 ] [ j ] + p [ i - 1 ] * p [ k ] * p [ j ] NEW_LINE if q < m [ i ] [ j ] : NEW_LINE INDENT m [ i ] [ j ] = q NEW_LINE DEDENT DEDENT DEDENT DEDENT return m [ 1 ] [ n - 1 ] NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 ] NEW_LINE size = len ( arr ) NEW_LINE print ( " Minimum ▁ number ▁ of ▁ multiplications ▁ is ▁ " + str ( MatrixChainOrder ( arr , size ) ) ) NEW_LINE