Matrix Chain Multiplication ( A O ( N ^ 2 ) Solution ) | CPP program to implement optimized matrix chain multiplication problem . ; 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
#include <iostream> NEW_LINE using namespace std ; int MatrixChainOrder ( int p [ ] , int n ) { int dp [ n ] [ n ] ; for ( int i = 1 ; i < n ; i ++ ) dp [ i ] [ i ] = 0 ; for ( int L = 1 ; L < n - 1 ; L ++ ) for ( int i = 1 ; i < n - L ; i ++ ) 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 ] ) ; return dp [ 1 ] [ n - 1 ] ; } int main ( ) { int arr [ ] = { 10 , 20 , 30 , 40 , 30 } ; int size = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printf ( " Minimum ▁ number ▁ of ▁ multiplications ▁ is ▁ % d ▁ " , MatrixChainOrder ( arr , size ) ) ; return 0 ; }