Шаг 1

Конечно, эту задачу легче всего решить динамическим программированием! Для этого мы будем продвигаться по всему массиву следующим образом. Сначала посмотрим на камни, до которых мы можем допрыгнуть. Выберем среди них один с самой большой цифрой и прыгнем на него. Это самое оптимальное локальное решение: ведь чем больше число, тем дальше оно сможет нас унести!

import {test} from "./tester";


function countJumps(pebbles) {
  return 0;
}

test(countJumps([2,3,1,1,4]), 2);

Шаг 2

Жадные алгоритмы невероятно простые, поэтому и наша демонстрация получилась в формате «возьмите и сделайте это». Однако не все задачи можно решить при помощи жадности! Об этом поговорим в следующей статье.

import {test} from "./tester";


function countJumps(pebbles) {
  let jumps = 0;

  let previousPosition = 0; // Позиция предыдущего оптимального прыжка
  let currentPosition = 0; // Позиция текущего прыжка

  // Пока не допрыгали до конца...
  while (currentPosition < pebbles.length - 1) {
    // Прыгаем!
    jumps++;

    // Нам нужно обойти все камни, которые мы можем достигнуть с предыдущего до текущего прыжка
    // Но так как дальше мы будем менять previousPosition, я заранее сохраняю его
    let candidate = previousPosition;

    // Текущий прыжок становится предыдущим
    previousPosition = currentPosition;

    while (candidate <= previousPosition) {
      // А текущий прыжок — это максимально достижимый камень с предыдущей
      currentPosition = Math.max(currentPosition, candidate + pebbles[candidate]);
      candidate++;
    }
  }

  return jumps;
}

test(countJumps([2,3,1,1,4]), 2);

File tester.js

const results = document.getElementById('results')

export function test(left, right) {
  const result = document.createElement('li');

  if (left === right) {
    result.innerHTML = "Тест пройден!";
    result.style.color = "green";
  } else {
    result.innerHTML = `Тест не пройден! ${left} не равно ${right}`;
    result.style.color = "red";
  }

  results.appendChild(result);
}