How would I solve this dynamic programming question with a table?

Question

Once again your are going on a long bike ride with your e-bike. You must ride exactly n miles. You will need 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 newly charged battery. There is one battery station at every mile marker. However, unlike in our class problem, there are a selection of m differently-sized battery options at each station. With all these options, you decide not to waste any battery charges. That means that for any battery you select, you must ride until it is empty before stopping to replace your battery. For example, at mile 0 if you pick a battery of size 3, you must ride 3 miles before changing your battery. The goal is to determine if it possible to arrive at mile marker n using this new energy-efficient approach.

1. The input to the problem is an array B[0 . . . n, 1 . . . m], where B[i, j] stores the battery life (in miles) of battery j at station i. For example, station 0 has battery sizes B[0, 1], B[0, 2], . . . , B[0, m]. Assume

you start the trail at mile 0, and that you may select to start with any of the batteries at that station. The output to your algorithm should be True if there is a route to mile n, and False otherwise. Provide a dynamic programming solution to this problem, and determine the runtime of your algorithm. You do not need to provide the list of stopping stations.

Answer 1

You could do it with something like this:

bool canReach(vector<vector<int>>& batteries, int start, vector<bool>& visited) {

// If we've gone past the end with a previous battery, then we can return true

if (start >= batteries.size()) {

return true;

}

// Otherwise, check if we've tried this before

if (visited[start]) {

return false;

}

// Then check if we can reach the end from here, recursively

for (int i=0; i<batteries[start].size(); i++) {

int charge = batteries[start][i];

if (canReach(grid, start+charge, visited)) {

return true;

}

}

// Finally, mark that we've tried and failed here and return out

visited[start] = true;

return false;

}