I've been given some homework on dynamic programming and I'm having trouble to find the suboptimal recurrence. Let me copy the statement:
In a given motorcycle training circuit, the number of riders is becoming increasingly large. As such, a new set of stricter rules is being enforced.
- Lap times last exactly a minute, and they are booked for the full minute.
- If we use a free lap time slot, we must wait x seconds until we can use another.
We are given a list {s1,s2,s3,...,sn} of the free slots starting time and we want to practice at least m minutes, at minimum. Find the maximum x that allows this.
Example:
With the list {00:00:00,00:10:03,00:14:00} and an m = 2 we can impose a maximum wait time of 00:14:00 - 00:01:00 = 00:13:00 = 1560s because we only need to lap two times, and we can do so with the first and last slot.
So I tried hard and came up with this recurrence: $$X[i,m] = \max_{1 \leq j \leq i}\ (\min\ (X[j,m-1],\sum_{k=j}^{n-1}abs(s_{k+1} - s_k)))$$ Where X[i,m] means "the maximum distance that I can pick in the subset $\{s_1,s_2,...,s_i\}$ so that I lap at least m times".
Then it's only a matter of applying dynamic programming. However, I'm not convinced that this solution is correct, because no matter how hard I try to make an algorithm out of it (using a matrix $X_{im}$) I can't come up with a good solution looking at the right bottom corner value (where i = n and m = laps requested).
Any ideas or hints?
Thank you.