Maximum path sum that starting with any cell of 0 | PHP program to find Maximum path sum start any column in row '0' and ends up to any column in row ' n - 1' ; function find maximum sum path ; create 2D matrix to store the sum of the path ; copy all element of first column into ' dp ' first column ; Find maximum path sum that end ups at any column of last row ' N - 1' ; return maximum sum path ; Driver Code
< ? php $ N = 4 ; function MaximumPath ( & $ Mat ) { global $ N ; $ result = 0 ; $ dp = array_fill ( 0 , $ N , array_fill ( 0 , $ N + 2 , NULL ) ) ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) $ dp [ 0 ] [ $ i + 1 ] = $ Mat [ 0 ] [ $ i ] ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) for ( $ j = 1 ; $ j <= $ N ; $ j ++ ) $ dp [ $ i ] [ $ j ] = max ( $ dp [ $ i - 1 ] [ $ j - 1 ] , max ( $ dp [ $ i - 1 ] [ $ j ] , $ dp [ $ i - 1 ] [ $ j + 1 ] ) ) + $ Mat [ $ i ] [ $ j - 1 ] ; for ( $ i = 0 ; $ i <= $ N ; $ i ++ ) $ result = max ( $ result , $ dp [ $ N - 1 ] [ $ i ] ) ; return $ result ; } $ Mat = array ( array ( 4 , 2 , 3 , 4 ) , array ( 2 , 9 , 1 , 10 ) , array ( 15 , 1 , 3 , 0 ) , array ( 16 , 92 , 41 , 44 ) ) ; echo MaximumPath ( $ Mat ) . " STRNEWLINE " ; ? >