Min Cost Path | DP | DP implementation of MCP problem ; Instead of following line , we can use int tc [ m + 1 ] [ n + 1 ] or dynamically allocate memory to save space . The following line is used to keep the program simple and make it working on all compilers . ; Initialize first column of total cost ( tc ) array ; Initialize first row of tc array ; Construct rest of the tc array ; returns minimum of 3 integers ; Driver Code
< ? php $ R = 3 ; $ C = 3 ; function minCost ( $ cost , $ m , $ n ) { global $ R ; global $ C ; $ tc ; for ( $ i = 0 ; $ i <= $ R ; $ i ++ ) for ( $ j = 0 ; $ j <= $ C ; $ j ++ ) $ tc [ $ i ] [ $ j ] = 0 ; $ tc [ 0 ] [ 0 ] = $ cost [ 0 ] [ 0 ] ; for ( $ i = 1 ; $ i <= $ m ; $ i ++ ) $ tc [ $ i ] [ 0 ] = $ tc [ $ i - 1 ] [ 0 ] + $ cost [ $ i ] [ 0 ] ; for ( $ j = 1 ; $ j <= $ n ; $ j ++ ) $ tc [ 0 ] [ $ j ] = $ tc [ 0 ] [ $ j - 1 ] + $ cost [ 0 ] [ $ j ] ; for ( $ i = 1 ; $ i <= $ m ; $ i ++ ) for ( $ j = 1 ; $ j <= $ n ; $ j ++ ) $ tc [ $ i ] [ $ j ] = min ( $ tc [ $ i - 1 ] [ $ j - 1 ] , $ tc [ $ i - 1 ] [ $ j ] , $ tc [ $ i ] [ $ j - 1 ] ) + $ cost [ $ i ] [ $ j ] ; return $ tc [ $ m ] [ $ n ] ; } $ cost = array ( array ( 1 , 2 , 3 ) , array ( 4 , 8 , 2 ) , array ( 1 , 5 , 3 ) ) ; echo minCost ( $ cost , 2 , 2 ) ; ? >