Dynamic Programming Pseudocode

Question

Suppose you are going on a long bike ride with your e-bike. You must ride exactly n miles. You will need to stop to replace your battery along the way. The bike trail is lined with battery pick-up stations, where you can trade your battery for a new charged battery. There is one battery station at every mile marker. However, the batteries at each station vary. For example, suppose that at station 1 they have batteries that last 3 miles, whereas station 2 may have batteries that last 7 miles. The goal is to complete the bike ride using the minimum number of stops to replace your battery. You cannot run out of power! If you pick up a battery pack worth 4 miles, then you cannot bike more than 4 miles! The input to the problem is an array b[0...n], where b[i] stores the battery life of the batteries at station i. The output is the minimum number of stops required. Assume you start the trail at mile 0, and that you receive the battery at station 0. Provide a dynamic programming solution, in just plain pseudocode, to this problem, and determine the runtime of your algorithm.

Answer 1

To use dynamic programming, we should have an array that stores the number of charges it would take to get to the end if we started at mile i. We'll call this array "dp" and initialize it to all 0's.

dp[] = { 0 }

And then our function can use this array to calculate our answer:

minimumStops ( b, startMile, endMile ) {

// First check our dp array to see if we've calculated this before

if (dp[startMile] != 0) {

return dp[startMile]

}

// Otherwise, charge up and see if we can reach the end with a single charge

charge = b[startMile]

if (charge >= endMile - startMile) {

dp[startMile] = 1

return 1

}

// If we can't, try recharging at every charging station within "charge" miles and see which one is the minimal

int charges = INT_MAX

for (int i=1; i<=charge && startMile + i < endMile; i++) {

charges = min(charges, minimumStops(b, startMile + i, endMile))

}

// Our answer is one more than that minimal number of charges

dp[startMile] = charges + 1;

return charges + 1;

}

And we can then just call this function with our starting conditions to find the answer:

minimumStops( b, 0, n );

As for the runtime performance of this algorithm, I think it's O(n*m), where n is the number of miles to travel and m is the average battery capacity at each pickup station, because that's the number of comparisons we have to do for every battery replacement to find the minimum.