Matrix Chain Multiplication ( A O ( N ^ 2 ) Solution ) | Matrix Mi 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 dp [ ] [ ] . 0 th row and 0 th column of dp [ ] [ ] are not used ; cost is zero when multiplying one matrix . ; Simply following above recursive formula . ; Driver code
def MatrixChainOrder ( p , n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT dp [ i ] [ i ] = 0 NEW_LINE DEDENT for L in range ( 1 , n - 1 ) : NEW_LINE INDENT for i in range ( n - L ) : NEW_LINE INDENT dp [ i ] [ i + L ] = min ( dp [ i + 1 ] [ i + L ] + p [ i - 1 ] * p [ i ] * p [ i + L ] , dp [ i ] [ i + L - 1 ] + p [ i - 1 ] * p [ i + L - 1 ] * p [ i + L ] ) NEW_LINE DEDENT DEDENT return dp [ 1 ] [ n - 1 ] NEW_LINE DEDENT arr = [ 10 , 20 , 30 , 40 , 30 ] NEW_LINE size = len ( arr ) NEW_LINE print ( " Minimum ▁ number ▁ of ▁ multiplications ▁ is " , MatrixChainOrder ( arr , size ) ) NEW_LINE