Минимальная сумма пути с препятствиями

Теперь каждая ячейка содержит значение, а Вам нужен самый дешёвый маршрут к углу. Цель меняется: вместо подсчёта путей нужно минимизировать стоимость.

Пусть dp[i][j] — наименьшая суммарная стоимость достижения ячейки (i, j). Сетка и ходы те же, но теперь мы отслеживаем суммы, а не количество путей.

Выбирайте из двух входящих соседей тот, путь через который дешевле, а затем прибавляйте значение текущей ячейки. Этот выбор минимума лежит в основе рекуррентной формулы.

Препятствие — это ячейка, на которую нельзя встать. Назначьте ей бесконечную стоимость, чтобы путь через неё никогда не оказался минимальным.

Если сетка помечает ячейку как заблокированную, просто установите для неё dp значение бесконечности и продолжайте. Шаг с выбором минимума естественным образом обойдёт её.

Если начальная ячейка заблокирована, пути вообще нет. Проверьте это сначала, чтобы не вернуть бессмысленную стоимость.

У начальной ячейки нет соседей, из которых можно прийти, поэтому её стоимость равна только её собственному значению. Установите dp[0][0] до запуска циклов.

Верхняя строка заполняется только слева, а левый столбец — только сверху. Обработайте эти границы, чтобы никогда не обращаться за пределы сетки.

Прибавление к бесконечности снова даёт бесконечность, поэтому полностью отрезанная ячейка сохраняет стоимость INF. Недостижимые ячейки автоматически показывают это.

Минимальная стоимость находится в правой нижней ячейке. Если там по-прежнему стоит бесконечность, допустимого пути вообще не существует.

Если всегда идти к соседней ячейке с меньшим значением, можно попасть в ловушку. Только полный DP гарантирует глобально самый дешёвый путь, а не жадный выбор на один шаг.

Выберите более дешёвого соседа и прибавьте значение ячейки, установите для заблокированных ячеек бесконечность и прочитайте значение в углу. INF в угловой ячейке означает отсутствие пути. 🧱