Matrix Chain Multiplication | DP | Python program using memoization ; Function for matrix chain multiplication ; Driver Code
import sys NEW_LINE dp = [ [ - 1 for i in range ( 100 ) ] for j in range ( 100 ) ] NEW_LINE def matrixChainMemoised ( p , i , j ) : NEW_LINE INDENT if ( i == j ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ j ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] NEW_LINE DEDENT dp [ i ] [ j ] = sys . maxsize NEW_LINE for k in range ( i , j ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i ] [ j ] , matrixChainMemoised ( p , i , k ) + matrixChainMemoised ( p , k + 1 , j ) + p [ i - 1 ] * p [ k ] * p [ j ] ) NEW_LINE DEDENT return dp [ i ] [ j ] NEW_LINE DEDENT def MatrixChainOrder ( p , n ) : NEW_LINE INDENT i = 1 NEW_LINE j = n - 1 NEW_LINE return matrixChainMemoised ( p , i , j ) NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Minimum ▁ number ▁ of ▁ multiplications ▁ is " , MatrixChainOrder ( arr , n ) ) NEW_LINE