Уникальные пути и минимальная сумма пути на сетках
Заполняйте двумерную таблицу DP для уникальных путей с препятствиями и без них, а затем адаптируйте её для минимизации суммы значений вдоль пути
«Уникальные пути и минимальная сумма пути на сетках» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Уникальные пути на сетке
Уникальные пути (LeetCode 62) — это задача о том, сколько различных путей ведёт в сетке размером m×n из верхнего левого угла в нижний правый, если двигаться можно только вправо или вниз. Для сетки размером 3×7 ответ равен 28. Ключевое наблюдение: каждый путь к ячейке (i,j) должен идти либо из (i-1,j) (сверху), либо из (i,j-1) (слева), что естественным образом приводит к двумерной формулировке DP.
# 3x7 grid: robot starts at (0,0), goes to (2,6)
# Must make exactly 2 down-moves and 6 right-moves
# Total moves = 8, choose 2 for down = C(8,2) = 28
import math
print('Unique paths 3x7:', math.comb(3+7-2, 3-1)) # 28
print('Unique paths 3x3:', math.comb(3+3-2, 3-1)) # 6
print('Unique paths 2x2:', math.comb(2+2-2, 2-1)) # 2Таблица двумерного DP для уникальных путей
Определим dp[i][j] как количество путей к ячейке (i,j). Вся первая строка и весь первый столбец состоят из единиц: до любой ячейки верхней строки или крайнего левого столбца можно добраться только одним способом. Для остальных ячеек: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Заполните таблицу построчно; ответом будет dp[m-1][n-1]. Временная сложность: O(m×n), память: O(m×n), которую можно сократить до O(n).
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
# First row and column stay as 1s (base cases)
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 3)) # 6
print(unique_paths(1, 1)) # 1 (already at destination)Оптимизация памяти до O(n)
Поскольку dp[i][j] зависит только от текущей и предыдущей строк, полную двумерную таблицу можно заменить одним одномерным массивом. Инициализируйте все значения единицами, а затем для каждой строки обновляйте массив на месте: dp[j] += dp[j-1]. После обработки строки i в dp[j] хранится значение, которое в двумерной таблице находилось бы в dp[i][j]. Это распространённый приём оптимизации задач двумерного DP.
def unique_paths_1d(m, n):
dp = [1] * n # initial row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # dp[j] was dp[i-1][j], dp[j-1] is dp[i][j-1]
return dp[n-1]
print(unique_paths_1d(3, 7)) # 28
print(unique_paths_1d(3, 3)) # 6
# Or use math for O(1)
import math
print(math.comb(3+7-2, 3-1)) # 28Уникальные пути II: препятствия
Уникальные пути II (LeetCode 63) добавляет в сетку препятствия (ячейки, отмеченные единицей). Любой путь через препятствие недопустим, поэтому dp[i][j] = 0, если obstacle[i][j] == 1. В противном случае рекуррентная формула остаётся прежней: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Если начальная или конечная ячейка заблокирована, ответ сразу равен 0. Тщательно инициализируйте базовые случаи: после появления единицы в первой строке или первом столбце все последующие ячейки этой строки или этого столбца равны 0.
def unique_paths_with_obstacles(obstacle_grid):
m, n = len(obstacle_grid), len(obstacle_grid[0])
dp = [[0] * n for _ in range(m)]
# First row
for j in range(n):
if obstacle_grid[0][j] == 1: break
dp[0][j] = 1
# First column
for i in range(m):
if obstacle_grid[i][0] == 1: break
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
if obstacle_grid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
grid = [[0,0,0],[0,1,0],[0,0,0]]
print(unique_paths_with_obstacles(grid)) # 2Задача о минимальной сумме пути
Минимальная сумма пути (LeetCode 64) — это задача о поиске в сетке размером m×n, заполненной неотрицательными целыми числами, пути из верхнего левого угла в нижний правый с минимальной суммой всех чисел на пути (двигаться можно только вправо или вниз). Например, в [[1,3,1],[1,5,1],[4,2,1]] путь 1→3→1→1→1 даёт сумму 7. Состояние DP такое же, как в задаче об уникальных путях, но теперь в рекуррентной формуле используется минимум, а не сложение.
grid = [[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
# Optimal path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
# Values: 1 + 3 + 1 + 1 + 1 = 7
print('Expected minimum path sum:', 7)Реализация DP для минимальной суммы пути
Определим dp[i][j] как минимальную стоимость достижения ячейки (i,j). Базовый случай: dp[0][0] = grid[0][0]. Первая строка: dp[0][j] = dp[0][j-1] + grid[0][j] (путь может прийти только слева). Первый столбец: dp[i][0] = dp[i-1][0] + grid[i][0] (путь может прийти только сверху). Общий случай: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Это прямое применение принципа оптимальности.
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0]
for j in range(1, n): # first row
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m): # first column
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7Минимальная сумма пути с изменением на месте
Если разрешено изменять входную сетку, можно обновлять её на месте, не выделяя отдельную таблицу DP. Это сокращает дополнительную память до O(1) (помимо входных данных). На собеседованиях иногда спрашивают об этой оптимизации — прежде чем применять её, уточните, разрешено ли изменять входные данные. Если нет, приём со скользящим одномерным массивом позволяет использовать O(n) памяти, не изменяя входные данные.
def min_path_sum_inplace(grid):
m, n = len(grid), len(grid[0])
# Mutate in place
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
if i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Минимальная сумма пути в треугольнике
Треугольник (LeetCode 120) — это задача о поиске минимальной суммы пути сверху вниз в массиве-треугольнике, где каждый шаг ведёт к соседнему числу в следующей строке. Проще всего использовать DP снизу вверх: начните со второй снизу строки и для каждой ячейки прибавляйте минимум из двух ячеек непосредственно под ней. Такой подход избавляет от необходимости отслеживать начальные индексы и естественным образом поднимает ответ к вершине.
def minimum_total(triangle):
# Bottom-up: start from second-to-last row
dp = triangle[-1][:] # copy of bottom row
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
dp[col] = triangle[row][col] + min(dp[col], dp[col+1])
return dp[0]
triangle = [
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
print(minimum_total(triangle)) # 11 (2+3+5+1)DP на сетке подземелья
Игра в подземелье (LeetCode 174) — это задача о поиске минимального начального запаса здоровья, необходимого для спасения принцессы в правом нижнем углу сетки с отрицательными (урон) и положительными (лечение) значениями в ячейках. Двигаться можно только вправо или вниз. Секрет в том, чтобы заполнять таблицу DP в обратном направлении (от правого нижнего угла к левому верхнему), вычисляя минимальный запас здоровья, необходимый в каждой ячейке. Для каждой ячейки: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Запас здоровья всегда должен оставаться не меньше 1.
def calculate_minimum_hp(dungeon):
m, n = len(dungeon), len(dungeon[0])
dp = [[0]*n for _ in range(m)]
# Fill from bottom-right
dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
for i in range(m-2, -1, -1): # last column
dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
for j in range(n-2, -1, -1): # last row
dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
need = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(1, need - dungeon[i][j])
return dp[0][0]
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
print(calculate_minimum_hp(dungeon)) # 7Сравнение задач DP на сетках
Задачи DP на сетках имеют общую структуру, но различаются направлением заполнения и операцией перехода: «Уникальные пути» использует сложение (подсчитывает все варианты). «Минимальная сумма пути» использует минимум (оптимизирует стоимость). «Игра в подземелье» заполняется в обратном направлении (определяет необходимый в будущем запас здоровья). При решении новой задачи DP на сетке задайте себе три вопроса: (1) Что представляет каждая ячейка? (2) В каком направлении следует заполнять таблицу? (3) Какая операция объединяет соседние значения? Ответы на эти три вопроса раскрывают всё решение.
# Summary: Grid DP Patterns
#
# Problem Fill Dir Transition
# Unique Paths top-left dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Unique Paths II top-left same but 0 if obstacle
# Min Path Sum top-left dp[i][j] = grid[i][j] + min(above, left)
# Triangle bottom-up dp[col] = row[col] + min(dp[col], dp[col+1])
# Dungeon bottom-right max(1, min(right, down) - cell)
# Recognise the pattern, write the transition, verify with examples
print('Grid DP summary complete')Итоги сложности DP на сетках
Все рассмотренные задачи DP на сетках требуют O(m×n) времени. Память варьируется от O(m×n) для полной таблицы до O(n) при использовании одномерного скользящего массива и до O(1) дополнительной памяти, если сетку можно изменять на месте. На собеседованиях после решения с памятью O(m×n) упомяните оптимизацию до O(n) — это показывает понимание компромиссов. Для всех задач также подумайте, существует ли жадное упрощение (например, математическая формула для уникальных путей).
# O(n) space version of Min Path Sum
def min_path_sum_1d(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
dp[0] += grid[i][0] # first column: only from above
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
return dp[n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_1d(grid)) # 7Быстрая проверка
Проверьте своё понимание концепций «Структуры данных и алгоритмы — подготовка к техническому собеседованию», рассмотренных в этом уроке.
Итоги урока
В этом уроке Вы узнали: задача «Уникальные пути» заполняет двумерную таблицу по формуле dp[i][j] = dp[i-1][j] + dp[i][j-1] и может быть вычислена за O(1) с помощью комбинаторики, задача «Минимальная сумма пути» использует ту же структуру, но заменяет сложение минимумом для поиска оптимальной стоимости пути, а также все задачи DP на сетках используют общий шаблон: определение состояния для каждой ячейки и выбор операции перехода (сумма, минимум, максимум). Далее мы рассмотрим задачу о наибольшей общей подпоследовательности с помощью двумерного DP для двух последовательностей.
Часто задаваемые вопросы
Урок «Уникальные пути и минимальная сумма пути на сетках» бесплатный?
Да — полный текст урока «Уникальные пути и минимальная сумма пути на сетках» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Уникальные пути и минимальная сумма пути на сетках»?
Заполняйте двумерную таблицу DP для уникальных путей с препятствиями и без них, а затем адаптируйте её для минимизации суммы значений вдоль пути Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Уникальные пути и минимальная сумма пути на сетках»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Уникальные пути и минимальная сумма пути на сетках
- Наибольшая общая подпоследовательность
- Расстояние редактирования (Левенштейна)
- Оптимизация памяти для двумерного DP