Unique Paths II

Средняя№63двумерная таблица

В сетке есть свободные клетки (0) и камни (1). Робот стартует в левом верхнем углу и шагает только вправо или вниз, на камни наступать нельзя. Посчитать маршруты до правого нижнего угла. Наш пример: [0, 0, 1, 0], [0, 0, 0, 0], [0, 1, 0, 0], 4 пути.

63 Unique Paths IIРазбор · 1×

Пример: сетка 3 × 4 с камнями в (0, 2) и (2, 1). Смотрите на (0, 3): камня нет, а путей 0 — камень перед ней перерезал верхнюю строку. И на (2, 2): все её пути приходят сверху.

0123012✕✕
пустопутей в эту клеткукаменьэтот шагберём отсюдаответ

Пустая таблица размером с сетку, 3 × 4; камни в (0, 2) и (2, 1)

01/38
сначала · назад · пуск · шаг
Скорость
1function uniquePathsWithObstacles(grid):
2 dp = table of the grid's size
3 for r from 0 to rows - 1:
4 for c from 0 to cols - 1:
5 if grid[r][c] == 1:
6 dp[r][c] = 0 // a rock: no path ends here
7 else if r == 0 and c == 0:
8 dp[r][c] = 1
9 else:
10 up = dp[r - 1][c] if r > 0 else 0
11 left = dp[r][c - 1] if c > 0 else 0
12 dp[r][c] = up + left
13 return dp[rows - 1][cols - 1]
состояние
dp
[[–, –, –, –], [–, –, –, –], [–, –, –, –]]
r
–
c
–
up
–
left
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Пути в свободную клетку — это пути в клетку сверху плюс пути в клетку слева, как и без камней: последний шаг приходит из одной из них.
  2. В камне 0, поэтому он ничего не добавляет клеткам за ним. Одно это убирает все пути через камень, и ни один путь не нужно проверять отдельно.
  3. Края больше не сплошные единицы: в верхнюю строку ведёт только прямая линия, а после камня она обрывается, поэтому в (0, 3) — 0.

Сложность

Время O(m × n): каждая клетка — одна проверка и одно сложение. Память O(m × n) на таблицу, или одна строка из n клеток: клетка читает только свою строку и строку над ней.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.