Минимальная сумма пути с препятствиями
Переносите минимальную стоимость через ячейки
«Минимальная сумма пути с препятствиями» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
От подсчёта к стоимости
Теперь каждая ячейка содержит значение, а Вам нужен самый дешёвый маршрут к углу. Цель меняется: вместо подсчёта путей нужно минимизировать стоимость.
Определите состояние
Пусть dp[i][j] — наименьшая суммарная стоимость достижения ячейки (i, j). Сетка и ходы те же, но теперь мы отслеживаем суммы, а не количество путей.
Переход
Выбирайте из двух входящих соседей тот, путь через который дешевле, а затем прибавляйте значение текущей ячейки. Этот выбор минимума лежит в основе рекуррентной формулы.
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])Отметьте препятствия
Препятствие — это ячейка, на которую нельзя встать. Назначьте ей бесконечную стоимость, чтобы путь через неё никогда не оказался минимальным.
INF = float('inf')Корректно блокируйте ячейки
Если сетка помечает ячейку как заблокированную, просто установите для неё dp значение бесконечности и продолжайте. Шаг с выбором минимума естественным образом обойдёт её.
if blocked(i, j):
dp[i][j] = INF
continueПроверьте начало
Если начальная ячейка заблокирована, пути вообще нет. Проверьте это сначала, чтобы не вернуть бессмысленную стоимость.
Инициализируйте первую ячейку
У начальной ячейки нет соседей, из которых можно прийти, поэтому её стоимость равна только её собственному значению. Установите dp[0][0] до запуска циклов.
dp[0][0] = grid[0][0]Обработайте границы
Верхняя строка заполняется только слева, а левый столбец — только сверху. Обработайте эти границы, чтобы никогда не обращаться за пределы сетки.
Бесконечность распространяется
Прибавление к бесконечности снова даёт бесконечность, поэтому полностью отрезанная ячейка сохраняет стоимость INF. Недостижимые ячейки автоматически показывают это.
Прочитайте результат
Минимальная стоимость находится в правой нижней ячейке. Если там по-прежнему стоит бесконечность, допустимого пути вообще не существует.
ans = dp[m-1][n-1]
if ans == INF:
ans = -1Когда жадный подход здесь не работает
Если всегда идти к соседней ячейке с меньшим значением, можно попасть в ловушку. Только полный DP гарантирует глобально самый дешёвый путь, а не жадный выбор на один шаг.
Быстрая проверка
Как сделать так, чтобы DP для путей обходил заблокированную ячейку без особой обработки каждого соседа?
Повторение: минимальный путь с препятствиями
Выберите более дешёвого соседа и прибавьте значение ячейки, установите для заблокированных ячеек бесконечность и прочитайте значение в углу. INF в угловой ячейке означает отсутствие пути. 🧱
Часто задаваемые вопросы
Урок «Минимальная сумма пути с препятствиями» бесплатный?
Да — полный текст урока «Минимальная сумма пути с препятствиями» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Минимальная сумма пути с препятствиями»?
Переносите минимальную стоимость через ячейки Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Минимальная сумма пути с препятствиями»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Подсчёт путей по сетке
- Минимальная сумма пути с препятствиями
- Наибольшая общая подпоследовательность
- Расстояние редактирования шаг за шагом