Блог

Это отличается от классической задачи codility Frog-River-одна с падающими в разное время листьями.

Постановка задачи

Есть часть, где она была отрезана: если обезьяна может просто перепрыгнуть реку, функция возвращает 0. Если невозможно перепрыгнуть реку, тогда -1.

Некоторые тестовые примеры включают:

[[-1, 5, -1, 5, -1, 10], 3] -> возвращает 5

[[1, -1, 0, 2, 3, 5], 3] -> возвращает 2

[[0, 0, 0, 0, 0, 0], 3] -> возвращает 0

На изображении есть описание проблемы. Я сделал это методом грубой силы, используя рекурсию, и хотя я считаю, что он вернул правильные ответы, вероятно, этого было недостаточно, потому что это дало бы время выполнения O (n ^ D) .

Есть ли способ решить эту проблему более эффективно? Чего я не вижу? Я чувствую, что может быть решение DP или простой математический трюк… Я прилагаю свое решение для справки.

Мое рекурсивное решение с объяснением

Обратите внимание, что самое раннее время, которого вы можете достичь x = i , может быть выражено следующим рекуррентным соотношением:

 shortest[i] = if A[i] = -1 then  inf 
              else max(A[i], min{shortest[j] | i - D <= j < i})
  

Итак, сначала есть простое O(ND) решение, использующее только динамическое программирование.

На самом деле это можно свести к O(N D) использованию эффективного алгоритма для поддержания минимума shortest в скользящем окне [i-D ... i] (с использованием двусторонней очереди).