@ above In that case , it will be a simple dynamic programming based recursion
assuming the total distance one has to cover is n ; d[i][j]=minimum number of fuel stations to stop at in order to cross i stations and with j miles still to go . dp[n][0]= minimum number of fuel stations to stop at in order cross n stations and with 0 miles still to go (Assuming the nth stop coincides with the destination B .In case it does not , we can answer something like dp[n][p] , where p is the distance to go from nth stop to A) The recursion dp[i][k]= min(dp[i+1][k- distance b/w the ith and (i+1)th fuel station] , dp[i+1][k- distance +lk]+1)(lk= distance we can cover on this stop) base case dp[0][j]=0;(for each j )// we have to cover no more stations therefore On Jan 22, 9:40 pm, Divya Jain <[email protected]> wrote: > if u can take only a certain amount of fuel from a particaular station ie > station xi can provide li amoutn of fuel.. then wat? > > On 22 January 2011 13:46, Terence <[email protected]> wrote: > > > > > Greedy-Approach. > > Refueling only when you have to. > > > On 2011-1-22 15:59, snehal jain wrote: > > >> Suppose you want to travel from city A to city B by car, following a > >> fixed route. Your car can travel m miles on a full tank of gas, and > >> you have a map of the n gas stations on the route between A and B that > >> gives the number of miles between each station. > >> Design an algorithm to find a way to get from A to B without running > >> out of gas that minimizes the total number of refueling stops, in O(n) > >> time. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<algogeeks%2Bunsubscribe@googlegroups > > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
