Maximum weight path ending at any element of last row in a matrix | Function which return the maximum weight path sum ; creat 2D matrix to store the sum of the path ; Initialize first column of total weight array ( dp [ i to N ] [ 0 ] ) ; Calculate rest path sum of weight matrix ; find the max weight path sum to rech the last row ; return maximum weight path sum ; Driver program
< ? php function maxCost ( $ mat , $ N ) { $ dp = array ( array ( ) ) ; memset ( dp , 0 , sizeof ( dp ) ) ; $ dp [ 0 ] [ 0 ] = $ mat [ 0 ] [ 0 ] ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) $ dp [ $ i ] [ 0 ] = $ mat [ $ i ] [ 0 ] + $ dp [ $ i - 1 ] [ 0 ] ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) { for ( $ j = 1 ; $ j < $ i + 1 && $ j < $ N ; $ j ++ ) $ dp [ $ i ] [ $ j ] = $ mat [ $ i ] [ $ j ] + max ( $ dp [ $ i - 1 ] [ $ j - 1 ] , $ dp [ $ i - 1 ] [ $ j ] ) ; } $ result = 0 ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) if ( $ result < $ dp [ $ N - 1 ] [ $ i ] ) $ result = $ dp [ $ N - 1 ] [ $ i ] ; return $ result ; } $ mat = array ( array ( 4 , 1 , 5 , 6 , 1 ) , array ( 2 , 9 , 2 , 11 , 10 ) , array ( 15 , 1 , 3 , 15 , 2 ) , array ( 16 , 92 , 41 , 4 , 3 ) , array ( 8 , 142 , 6 , 4 , 8 ) ) ; $ N = 5 ; echo " Maximum ▁ Path ▁ Sum ▁ : ▁ " , maxCost ( $ mat , $ N ) ; ? >