Самый быстрый алгоритм для прыжка через массив

Начните с массива на положительные числа. Начните по индексу 0. От индекса I можно перейти к индексу I + X для любого x <= A [i]. Цель состоит в том, чтобы найти минимальное количество ходов, необходимых для дохода до конца массива.

Вот пример:

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

Если вы всегда идете как можно дальше в каждом ходу, то это то, что вы получаете:

0 , 2 , 3 , 5 , 7

Это занимает 4 хода. Но вы можете пройти через него быстрее, сделав это таким образом

0 , 1 , 4 , 7

Это только требуется 3 хода.

Я немного подумал об этом и сделал первое, о чем я думал, но после еще на несколько дней я до сих пор не знаю, как это сделать лучше.

Вот моя идея. Начните в конце массива и отслеживать минимальное количество перемещений из некоторого положения до конца. Так что для примера движется [7] = 0 , потому что это уже конец. Затем движется [6] = 1 , потому что это займет один шаг, чтобы дойти до конца. Моя формула

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

к тому времени, когда я доберусь до начала, я знаю количество ходов.

Так что это O (n ^ 2), что в порядке, я думаю, но, вероятно, есть быстрее?