Fastest algorithm to hop through an array

Question

Start with an array A of positive numbers. Start at index 0. From index i, you can move to index i+x for any x <= A[i]. The goal is to find the minimum number of moves needed to get to the end of the array.

Here's an example:

{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2} 

If you always go as far as possible in each move, then this is what you get:

0 , 2 , 3 , 5 , 7

This takes 4 moves. But you can get through it faster by doing it this way

0 , 1 , 4 , 7

This only takes 3 moves.

I thought about this for a bit and did the first thing I thought of, but after thinking for a few more days, I still don't know how to do it any better.

Here's my idea. Start at the end of the array and keep track of the minimum number of moves from some position to the end. So for the example, moves[7] = 0 because it's the end already. Then moves[6] = 1 because it takes one move to get to the end. My formula is

moves[i] = 1 + min(moves[i+1], moves[i+2], ... , moves[i+A[i]])

By the time I get to the beginning, I know the number of moves.

So this is O(n^2) which is okay I guess, but probably there is a faster way?

Answer 1

Since you can chose any x in [1,A[i]] I guess there is a pretty simple solution :

start at 0:

select the next reachable element from which you can reach the farther element. i.e chose i that maximize i+A[i+x] for x in [1,A[i]]

until you arrive at the end of the list.

---

Example:

{2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}

start at 0

from 0 you can get to 1 or to 2:

• from 1 you can get to 4
• from 2 you can get to 3

therefore max(0+A[0+x]) is for i = 1

chose 1 from 1 you can get to 2 3 4:

• from 4 you can get to 7
• from 3 you can get to 5
• from 2 you can get to 3

therefore max(1+A[1+x]) is for i = 4

chose 4

you can reach 7

stop

the resulting list is : 

0,1,4,7

As explained in my comments I think it's O(N), because from i you reach i+x+1 in at least 2*x operations.

---

'Pseudo' proof

You start at 0 (it's optimal)

then you select i that maximize(0+A[0+x]) (i.e that maximize the reachability for the next element)

from that i you can reach any other element that is reachable from all other elements reachable from 0 (it's a long sentence, but it means : who can do more, can do less, therefore if i is not optimal,it's as good as optimal)

So i is optimal

then following step by step this reasoning, it proves the optimality of the method.

If someone knows how to formulate that more mathematically, feel free to update it.