Find the minimum cost to reach destination using a train | A Dynamic Programming based solution to find min cost to reach station N - 1 from station 0. ; This function returns the smallest possible cost to reach station N - 1 from station 0. ; dist [ i ] stores minimum cost to reach station i from station 0. ; Go through every station and check if using it as an intermediate station gives better path ; Driver program to test above function
< ? php $ INF = PHP_INT_MAX ; $ N = 4 ; function minCost ( $ cost ) { global $ INF ; global $ N ; $ dist [ $ N ] = array ( ) ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) $ dist [ $ i ] = $ INF ; $ dist [ 0 ] = 0 ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) for ( $ j = $ i + 1 ; $ j < $ N ; $ j ++ ) if ( $ dist [ $ j ] > $ dist [ $ i ] + $ cost [ $ i ] [ $ j ] ) $ dist [ $ j ] = $ dist [ $ i ] + $ cost [ $ i ] [ $ j ] ; return $ dist [ $ N - 1 ] ; } $ cost = array ( array ( 0 , 15 , 80 , 90 ) , array ( INF , 0 , 40 , 50 ) , array ( INF , INF , 0 , 70 ) , array ( INF , INF , INF , 0 ) ) ; echo " The ▁ Minimum ▁ cost ▁ to ▁ reach ▁ station ▁ " , $ N , " ▁ is ▁ " , minCost ( $ cost ) ; ? >