Войти Регистрация
Алгоритмы

192. Путь погрузчика с наименьшей задержкой

Средняя

Зона склада Wildberries — сетка delay: delay[i][j] — сколько секунд погрузчик теряет в клетке (очередь у стеллажа, узкий проход).

Погрузчик едет из левой верхней клетки в правую нижнюю, каждым шагом вправо или вниз. Верните наименьшую суммарную задержку, считая начальную и конечную клетки.

В работе: Система раздачи заданий строит маршрут на каждый вывоз паллеты: на зоне 400 × 300 ячеек путей порядка 10²⁰⁰, а ответ нужен за десятки миллисекунд.

Пример 1

Ввод
delay = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Вывод
7

Вправо, вправо, вниз, вниз: 1 + 3 + 1 + 1 + 1 = 7.

Пример 2

Ввод
delay = [[9]]
Вывод
9

Старт совпадает с финишем.

Ограничения

  • 1 ≤ h, w ≤ 1000
  • 0 ≤ delay[i][j] ≤ 1000
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def min_delay_path(delay):
Динамическое программированиеДП на сеткеМатрицацельO(n)

Источник: наша задача на данных Wildberries. Условие пересказано своими словами.