Hello,

So I’ve have the following problem to solve:

Let’s take an animal, here a bear. The bear is placed at position 0 on a straight line of length L (0, 1, 2, …, L-1). There are several traps on the line indicated by the array traps[]. The bear can walk from position i to position i+1, or he can jump from position i to position i+J. J is the number of position he can jump during one single jump. The bear can always jump excactly J positions, not less not more.

The task is to find the furthest distance the bear can move without getting into a trap!

So here’s an example:

L = 15

J = 4

traps = {4, 6, 8, 11, 13, 14}

-> 0, 1, 2, 3, **4**, 5, **6**, 7, **8**, 9, 10, **11**, 12, **13**, **14**

The bear can move maximum to position 10.

It first moves to 1, then jumps to 5, jumps again to 9 and then finally moves 1 further to 10.

It can’t move from 9 to 13 as there is a trap, neither from 2 to 6, etc.

Is there an algorithm that finds the furthest distance the bear can get? And how does it work?

I was thinking of an algorithm that uses recursion or maybe using dynamic programming?