Достижим ли конец списка прыжками: что даёт жадность
В списке nums неотрицательные числа: nums[i] — максимальная длина прыжка из позиции i (можно прыгнуть и короче). Старт в позиции 0, надо определить, достижима ли последняя позиция.
nums = [3, 2, 1, 0, 4]
Какое утверждение верно?
- Хватает одного прохода жадностью по максимальной достижимой позиции: конец недостижим
- Жадность неприменима: нужна динамика за O(n^2), перебирающая все прыжки из каждой позиции
- Достаточно проверить, что в списке нет нулей: застрять можно только на нулевом элементе
- Надо всегда прыгать ровно на nums[i] шагов: для этого списка такой ход приводит в конец