Matrix Chain Multiplication ( A O ( N ^ 2 ) Solution ) | Java 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
import java . util . * ; import java . lang . * ; import java . io . * ; class GFG { static int MatrixChainOrder ( int p [ ] , int n ) { int [ ] [ ] dp = new int [ 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 ] = Math . 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 ] ; } public static void main ( String args [ ] ) { int arr [ ] = { 10 , 20 , 30 , 40 , 30 } ; int size = arr . length ; System . out . print ( " Minimum ▁ number ▁ of ▁ multiplications ▁ is ▁ " + MatrixChainOrder ( arr , size ) ) ; } }