@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.comalgogeeks%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.
