Putting the decision off, and starting over

What is the fewest jumps to the end? Again you pick no box; this time you think in layers. Walk all the boxes one jump can reach and find the farthest point reachable from them: that is the edge of the layer two jumps reach. When you arrive at an edge, count one jump.

1jumps = edge = farthest = 0
2for i in range(len(values) - 1):
3    farthest = max(farthest, i + values[i])
4    if i == edge:
5        jumps += 1
6        edge = farthest
7return jumps

edge is the last box reachable with the current number of jumps. Until you get to it you gather "how far could the next jump take me at most"; you never decide which box to jump from. The loop does not enter the last box: there is no need to jump from there.

For gas stations on a circle another greedy idea works: if you set out from some start and the tank goes negative at some point, then no station in that stretch is a good start (you reached each with at least zero fuel and it still was not enough). You start over from the next station and never try any start twice.

Tasks