Matrix Chain Multiplication | DP | A naive recursive implementation that simply follows the above optimal substructure property ; Matrix A [ i ] has dimension p [ i - 1 ] x p [ i ] for i = 1. . n ; place parenthesis at different places between first and last matrix , recursively calculate count of multiplications for each parenthesis placement and return the minimum count ; Return minimum count ; Driver code
import sys NEW_LINE def MatrixChainOrder ( p , i , j ) : NEW_LINE INDENT if i == j : NEW_LINE INDENT return 0 NEW_LINE DEDENT _min = sys . maxsize NEW_LINE for k in range ( i , j ) : NEW_LINE INDENT count = ( MatrixChainOrder ( p , i , k ) + MatrixChainOrder ( p , k + 1 , j ) + p [ i - 1 ] * p [ k ] * p [ j ] ) NEW_LINE if count < _min : NEW_LINE INDENT _min = count NEW_LINE DEDENT DEDENT return _min NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 , 3 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Minimum ▁ number ▁ of ▁ multiplications ▁ is ▁ " , MatrixChainOrder ( arr , 1 , n - 1 ) ) NEW_LINE