@above How can you calculate dp[n][0] with above recursive eq??
On Jan 23, 5:40 pm, sankalp srivastava <richi.sankalp1...@gmail.com> wrote: > @ 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 <sweetdivya....@gmail.com> 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 <technic....@gmail.com> 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 algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com<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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
