Подсчёт путей по сетке
Суммируйте пути от одного угла до другого
«Подсчёт путей по сетке» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Классическая задача на сетке
Вы начинаете в левом верхнем углу сетки и хотите попасть в правый нижний. Каждый шаг ведёт вправо или вниз. Сколько существует различных путей?
Почему здесь подходит DP
В каждую ячейку можно попасть из ячейки сверху или из ячейки слева. Именно это перекрытие делает задачу задачей на DP.
Определите состояние
Пусть dp[i][j] — количество способов попасть из начала в ячейку (i, j). Чёткое определение состояния — уже половина решения.
Переход
В ячейку можно прийти только сверху или слева, поэтому количество способов равно их сумме. Именно этот переход определяет всю таблицу.
dp[i][j] = dp[i-1][j] + dp[i][j-1]Базовый случай
До начальной ячейки можно добраться ровно одним способом: ничего не делать. Поэтому dp[0][0] равно 1 до заполнения остальных ячеек.
dp[0][0] = 1На границах есть один путь
В ячейках верхней строки или левого столбца есть только один прямой маршрут. Их количество всегда равно 1, поскольку один из соседей находится за пределами сетки.
Постройте таблицу
Создайте таблицу размера m на n, заполненную нулями. Заранее выбранный размер упрощает индексацию и предотвращает неожиданности.
dp = [[0] * n for _ in range(m)]Заполняйте в порядке чтения
Перебирайте сначала строки, затем столбцы — сверху вниз и слева направо. Такой порядок гарантирует, что оба соседа будут готовы до их использования.
for i in range(m):
for j in range(n):
...Ячейка с ответом
После заполнения таблицы количество путей находится в последней ячейке. Ответ — это dp[m-1][n-1], правый нижний угол.
answer = dp[m-1][n-1]Экономьте память с одной строкой
Для каждой строки нужна только строка выше, поэтому можно хранить одну строку и обновлять её на месте. Это сокращает объём памяти до O(n).
row[j] += row[j-1]Математическое упрощение
Если препятствий нет, ответ задаётся биномиальным коэффициентом: нужно выбрать, какие из общего числа шагов будут направлены вниз. Но при появлении препятствий DP всё равно оказывается удобнее.
Быстрая проверка
Вы заполняете dp[i][j] для свободной внутренней ячейки. Какая формула верна?
Повторение: подсчёт путей
Определите dp как количество путей до ячейки, установите dp[0][0] равным 1 и сложите значения ячейки сверху и ячейки слева. В угловой ячейке находится ваш ответ. 🧭
Часто задаваемые вопросы
Урок «Подсчёт путей по сетке» бесплатный?
Да — полный текст урока «Подсчёт путей по сетке» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Подсчёт путей по сетке»?
Суммируйте пути от одного угла до другого Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Подсчёт путей по сетке»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Подсчёт путей по сетке
- Минимальная сумма пути с препятствиями
- Наибольшая общая подпоследовательность
- Расстояние редактирования шаг за шагом