Unique Paths

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

Робот стоит в левом верхнем углу сетки из m строк и n столбцов и должен дойти до правого нижнего угла. Шагать можно только вправо или вниз. Посчитать, сколько у него разных маршрутов. Наш пример: сетка 3 × 4, 10 путей.

62 Unique PathsРазбор · 1×

Пример: сетка 3 × 4. Смотрите на последнюю клетку: сверху приходят 4 пути, слева 6, вместе они и дают ответ.

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

Пустая таблица: 3 строки, 4 столбца, по клетке на каждую клетку сетки

01/28
сначала · назад · пуск · шаг
Скорость
1function uniquePaths(m, n):
2 dp = table of m rows and n columns
3 for c from 0 to n - 1:
4 dp[0][c] = 1 // the top row: only moves right
5 for r from 1 to m - 1:
6 dp[r][0] = 1 // the left column: only moves down
7 for c from 1 to n - 1:
8 up = dp[r - 1][c]
9 left = dp[r][c - 1]
10 dp[r][c] = up + left
11 return dp[m - 1][n - 1]
состояние
dp
[[–, –, –, –], [–, –, –, –], [–, –, –, –]]
r
–
c
–
up
–
left
–
историянажмите шаг, чтобы вернуться

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

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

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

Сложность

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

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

Решить на LeetCode ↗

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