Unique Paths: число путей в сетке через ДП и сочетания

Коротко

Робот идёт из левого верхнего угла сетки $m \times n$ в правый нижний, только вправо и вниз. Сколько существует разных путей?

• Идея ДП: в клетку можно прийти только сверху или слева, поэтому путей в неё столько, сколько в те две клетки вместе.
• Идея формулы: любой путь — это строка из $m-1$ букв «вниз» и $n-1$ букв «вправо». Выбираем, на каких позициях стоят «вниз».
• Что дальше на интервью: почти наверняка препятствия. Формула на них ломается, а ДП меняется на две строки.

Условие

Сетка из $m$ строк и $n$ столбцов. Робот стартует в клетке (0, 0), финиш — в (m-1, n-1). Шаг вправо или вниз, других ходов нет. Нужно посчитать количество различных путей.

m = 3, n = 2  ->  3
  вниз, вниз, вправо
  вниз, вправо, вниз
  вправо, вниз, вниз

m = 3, n = 7  ->  28

На LeetCode это задача 62: $1 \le m, n \le 100$, а тесты подобраны так, что ответ не больше $2 \cdot 10^9$. Эта оговорка ещё пригодится: без неё сетка $100 \times 100$ дала бы число из 59 цифр.

Откуда берётся сумма

Посмотрите на последний шаг любого пути в клетку (i, j). Он сделан либо сверху, из (i-1, j), либо слева, из (i, j-1). Третьего варианта нет, и один путь не может закончиться сразу обоими способами. Значит, множества путей не пересекаются, и их размеры можно просто сложить:

База: в клетки верхней строки и левого столбца ведёт ровно один путь. По верхней строке можно только идти вправо, по левому столбцу — только вниз.

Заодно видно, почему тут вообще работает динамика: робот не возвращается назад, поэтому зависимости между клетками не образуют циклов. Запомните это, в конце статьи мы встретим задачу, где это условие нарушено.

Наивная рекурсия

Формула переписывается в код один к одному:

def unique_paths(m, n):
    if m == 1 or n == 1:
        return 1
    return unique_paths(m - 1, n) + unique_paths(m, n - 1)

Код верный, но есть забавное наблюдение про его скорость. Единственное, что эта функция возвращает из базы, — единица. То есть ответ собирается сложением единиц, и листьев в дереве вызовов ровно столько, сколько путей. Дерево бинарное, поэтому всего вызовов будет $2 \cdot \text{ответ} - 1$:

Время замерено на одной машине, важен порядок, а не точные цифры. На каждый шаг вперёд по диагонали — примерно в четыре раза дольше.

Причина знакомая: одни и те же клетки считаются снова и снова. Кэш это лечит:

from functools import cache


@cache
def unique_paths(m, n):
    if m == 1 or n == 1:
        return 1
    return unique_paths(m - 1, n) + unique_paths(m, n - 1)

Теперь каждая клетка считается один раз: время и память $O(m \cdot n)$. Глубина рекурсии доходит до $m + n$, для ограничений задачи это терпимо, а вот сетка $1000 \times 1000$ упадёт с RecursionError при стандартном лимите. Подробнее о приёме — в статье про мемоизацию.

Двумерная таблица

То же самое снизу вверх, без рекурсии. Заполняем клетки так, чтобы верхняя и левая к моменту расчёта уже были готовы, то есть обычным обходом по строкам:

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    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]

Таблица для $m = 3$, $n = 7$:

Проверьте любую клетку: $15 = 5 + 10$, $21 = 6 + 15$, $28 = 7 + 21$. Время и память $O(m \cdot n)$.

На интервью с этого варианта удобно начинать: он пишется за пару минут и не требует объяснений сверх рекуррентной формулы. Если с двумерными таблицами пока неуверенно, начните с введения в динамическое программирование.

Сжатие до одной строки

Посмотрите, что на самом деле нужно для клетки (i, j): значение из предыдущей строки в том же столбце и значение из текущей строки слева. Вся остальная таблица уже не используется, а значит, её можно не хранить.

Заводим один массив. Когда мы стоим на позиции j и ещё не обновили её:

• row[j] хранит значение с прошлой строки, то есть «сверху»;
• row[j - 1] уже обновлён на этой строке, то есть это «слева».

def unique_paths(m, n):
    if m < n:
        m, n = n, m
    row = [1] * n
    for _ in range(m - 1):
        for j in range(1, n):
            row[j] += row[j - 1]
    return row[-1]

Массив для $m = 3$, $n = 7$ проходит те же значения, что и строки таблицы:

старт:     [1, 1, 1, 1,  1,  1,  1]
проход 1:  [1, 2, 3, 4,  5,  6,  7]
проход 2:  [1, 3, 6, 10, 15, 21, 28]

Две детали, о которых стоит сказать вслух.

Обмен m и n. Ответ симметричен: сетка $3 \times 7$ и сетка $7 \times 3$ дают одно и то же. Поэтому строку можно сделать по короткой стороне, и память станет $O(\min(m, n))$, а не просто $O(n)$. Время остаётся $O(m \cdot n)$.

Направление обхода. Идти нужно слева направо, потому что нам нужно уже новое значение слева. Если развернуть цикл, на сетке $3 \times 7$ получится 4 вместо 28. В рюкзаке 0/1 всё наоборот: там обе зависимости лежат в предыдущей строке, поэтому при сжатии идут справа налево, чтобы не затереть старые значения. Универсального правила нет, каждый раз смотрите, откуда берутся данные.

Баг, который проходит тесты

Классическая ошибка новичка в Python — создать таблицу так:

def unique_paths(m, n):
    dp = [[1] * n] * m  # все строки — один и тот же список
    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]

Обычно это приводит к мусору в ответе, но здесь код выдаёт верный результат на любых входах. Дело в том, что когда все строки указывают на один список, dp[i - 1][j] и dp[i][j - 1] читают из него же, и получается ровно сжатие до одной строки, просто случайно написанное. Для $3 \times 4$ в dp лежит [[1, 3, 6, 10], [1, 3, 6, 10], [1, 3, 6, 10]].

Ответ верный, но таблицы как таковой нет. Как только понадобится восстановить путь или посмотреть промежуточные значения, там окажется неправда. Пишите [[1] * n for _ in range(m)].

Формула через сочетания

Теперь забудем про клетки. Чтобы дойти до финиша, робот должен сделать ровно $m-1$ шаг вниз и $n-1$ шаг вправо, всего $m + n - 2$ шага. Порядок любой: робот не может выйти за край, не сделав лишних шагов, а лишних у него нет.

Значит, путь — это просто строка длины $m + n - 2$ из букв D и R, и разным строкам соответствуют разные пути. Для $m = 3$, $n = 2$ их три: DDR, DRD, RDD.

Чтобы задать такую строку, достаточно выбрать, на каких позициях стоят D. Это сочетания:

Проверка: $m = 3$, $n = 7$ даёт $\binom{8}{2} = 28$.

Это не совпадение с таблицей выше. Наша рекуррентная формула — то же самое правило Паскаля $\binom{k}{r} = \binom{k-1}{r-1} + \binom{k-1}{r}$, а таблица ДП — повёрнутый на 45° треугольник Паскаля. Так что две задачи на самом деле одна.

Считаем без факториалов

Факториалы считать незачем: они огромные, а в итоге почти всё сокращается. Пусть $a = \max(m, n) - 1$ и $k = \min(m, n) - 1$. Тогда:

def unique_paths(m, n):
    a = max(m, n) - 1
    k = min(m, n) - 1
    res = 1
    for i in range(1, k + 1):
        res = res * (a + i) // i
    return res

Цикл из $\min(m, n) - 1$ итераций и никакой дополнительной памяти, поэтому время $O(\min(m, n))$, память $O(1)$. Для $1 \times 1$ цикл не выполнится ни разу, и получится правильная единица (пустой путь).

Почему целочисленное деление здесь честное? После шага $i$ в res лежит $\binom{a+i}{i}$, а это целое число. Значит, произведение res * (a + i) обязательно делится на i нацело. Но только в таком порядке: сначала умножить, потом разделить.

В Python такой цикл можно не писать: есть math.comb(m + n - 2, m - 1) (с версии 3.8). На интервью скажите о нём, но будьте готовы написать цикл руками.

Честно про сложность

Оценка $O(\min(m, n))$ считает арифметические операции и предполагает, что каждая стоит $O(1)$. С гарантией LeetCode это правда: все числа помещаются в 64 бита. Более того, $18 \times 18$ уже даёт больше $2 \cdot 10^9$, поэтому $\min(m, n) \le 17$ и цикл делает максимум 16 итераций.

Без гарантии числа становятся длинными, и умножение перестаёт быть константным: для $100 \times 100$ ответ — это 59 цифр. Python возьмёт длинную арифметику на себя, но если на интервью спросят про такие размеры, эту оговорку стоит сделать. На практике формула всё равно сильно быстрее: на сетке $1000 \times 1000$ у меня строка считается порядка сотни миллисекунд, формула — доли миллисекунды.

Где формула ломается в коде

Вся сложность цикла сидит в одной строке. Вот что бывает, если написать её небрежно:

Первая и последняя строки — потеря точности в float и number: промежуточное произведение вылезает за $2^{53}$, хотя сам ответ ещё нет. Вторая — деление раньше умножения. Третья интереснее всего: ответ в int помещается, а произведение res * (a + i) — нет.

В Java хватает long. Промежуточные res растут и не превышают ответа, поэтому произведение не больше $2 \cdot 10^9 \cdot 198$:

class Solution {
    public int uniquePaths(int m, int n) {
        int a = Math.max(m, n) - 1;
        int k = Math.min(m, n) - 1;
        long res = 1;
        for (int i = 1; i <= k; i++) {
            res = res * (a + i) / i;
        }
        return (int) res;
    }
}

В JavaScript для больших сеток нужен BigInt:

function uniquePaths(m, n) {
  const a = BigInt(Math.max(m, n) - 1)
  const k = BigInt(Math.min(m, n) - 1)
  let res = 1n
  for (let i = 1n; i <= k; i++) {
    res = (res * (a + i)) / i
  }
  return res
}

Продолжение: Unique Paths II

Самый вероятный следующий вопрос — задача 63 с LeetCode. В сетке есть препятствия: 1 означает, что клетка занята, 0 — что свободна. Сколько теперь путей?

Формула здесь сдаётся сразу: не все строки из D и R теперь допустимы, и какие именно отпали, зависит от расположения препятствий. А вот ДП почти не меняется: в занятую клетку ведёт ноль путей.

def unique_paths_with_obstacles(grid):
    n = len(grid[0])
    row = [0] * n
    row[0] = 1
    for cells in grid:
        for j, cell in enumerate(cells):
            if cell == 1:
                row[j] = 0
            elif j > 0:
                row[j] += row[j - 1]
    return row[-1]

Прогон на сетке с препятствием в центре:

grid:            row после прохода:
0 0 0            [1, 1, 1]
0 1 0            [1, 0, 1]
0 0 0            [1, 1, 2]   -> ответ 2

Обратите внимание: здесь нет отдельной инициализации верхней строки и левого столбца. Они считаются общим циклом, и это не для красоты, а чтобы обойти сразу несколько ловушек.

Ловушки

Единицы в первой строке и столбце. В чистой задаче там всегда единицы, и рука сама пишет [[1] * n for _ in range(m)]. Но препятствие перекрывает всё, что за ним: на сетке [[0, 1, 0]] такая инициализация даёт 1, а правильный ответ — 0.

Препятствие на старте или финише. Это допустимый вход, и ответ тогда 0. В коде выше оба случая обрабатываются сами: стартовая единица обнулится на первой же итерации, а занятый финиш обнулит row[-1]. Проверьте [[1]] на интервью вслух, это хороший тест.

Левый столбец в сжатой версии. Элемент row[0] переходит между строками как есть, и заново его ставить в единицу нельзя. Если препятствие обнулило его, все клетки ниже в этом столбце тоже недостижимы.

Значения больше ответа. Здесь есть тонкость, которой нет в чистой задаче. Возьмите сетку $100 \times 100$ и закройте обе клетки рядом с финишем. Ответ — 0, ограничение на ответ соблюдено, а где-то посреди сетки лежит число порядка $5{,}7 \cdot 10^{57}$. Оно не помещается ни в int, ни в long.

На ответ такие числа не влияют. Если из клетки можно дойти до финиша, то каждый путь в неё продолжается до финиша хотя бы одним способом, и разные пути остаются разными, поэтому значение в ней не больше ответа. Большие числа живут только в тупиках, откуда финиш недостижим, и в живые клетки они не перетекают. Что это значит на практике:

• Python: длинная арифметика, проблемы нет.
• Java: int тихо переполняется по модулю $2^{32}$, а итоговый ответ всё равно верный.
• JavaScript: точность теряется только в тупиках, ответ не страдает.
• C++: переполнение знакового типа — неопределённое поведение, и с включённым санитайзером программа сообщит об ошибке. Нужен беззнаковый тип вроде unsigned long long, у него переполнение определено.

Мало препятствий на огромной сетке

Бывает и обратная постановка: сетка $10^5 \times 10^5$, препятствий пара тысяч, ответ по модулю $10^9 + 7$. Таблица не влезет, и формула неожиданно возвращается. Эта задача скорее из олимпиадной практики: на AtCoder она есть как Grid 2 в Educational DP Contest, на Codeforces — как 559C.

Отсортируем препятствия, а финиш поставим последней точкой. Для каждой точки $p_i$ считаем $\text{clean}_i$ — число путей до неё, которые не проходят ни через одно препятствие раньше. Каждый плохой путь однозначно разбивается по первому препятствию на своём пути, поэтому:

где $\text{ways}$ — обычные сочетания без препятствий.

MOD = 10**9 + 7


def paths_with_few_obstacles(m, n, blocked):
    size = m + n
    fact = [1] * size
    for i in range(1, size):
        fact[i] = fact[i - 1] * i % MOD
    inv = [1] * size
    inv[-1] = pow(fact[-1], MOD - 2, MOD)
    for i in range(size - 1, 0, -1):
        inv[i - 1] = inv[i] * i % MOD

    def ways(a, b):
        dr, dc = b[0] - a[0], b[1] - a[1]
        if dr < 0 or dc < 0:
            return 0
        return fact[dr + dc] * inv[dr] % MOD * inv[dc] % MOD

    points = sorted(blocked) + [(m - 1, n - 1)]
    clean = []
    for i, p in enumerate(points):
        cur = ways((0, 0), p)
        for j in range(i):
            cur -= clean[j] * ways(points[j], p)
        clean.append(cur % MOD)
    return clean[-1]

Сложность $O(m + n + k^2)$, где $k$ — число препятствий. Сортировка гарантирует, что любое препятствие, через которое можно пройти на пути к $p_i$, стоит в списке раньше. Деление по модулю заменено на умножение на обратный элемент: подробнее в статье про модульную арифметику. Я сверил этот код с обычным ДП на тысячах случайных сеток и с примерами к задаче 559C.

Какие ещё вопросы зададут

Unique Paths хороша тем, что от неё легко ответвиться. Вот что стоит прикинуть заранее (общие советы по таким вопросам — в статье про follow-up на интервью):

На последней строке стоит остановиться. Помните замечание про отсутствие циклов? Как только робот может ходить во все стороны, клетка зависит от соседей, а соседи от неё, и порядка заполнения таблицы просто нет. Поэтому там сетка совсем маленькая, $m \cdot n \le 20$, и решают её перебором с возвратом либо ДП по маскам, где состояние — это не клетка, а клетка плюс множество посещённых.

Типичные ошибки

• Считать клетки вместо ходов. $\binom{m+n}{m}$ для $3 \times 7$ даёт 120 вместо 28. Ходов на два меньше, чем $m + n$: $m-1$ вниз и $n-1$ вправо.
• Считать полные факториалы в Java или C++. $21!$ уже не помещается в long. Используйте произведение из раздела выше.
• Использовать / вместо // в Python. На маленьких тестах всё сойдётся, а на $27 \times 30$ ответ уедет на единицу.
• Обходить сжатую строку справа налево по привычке из рюкзака.
• Путать m и n и не замечать этого. В чистой задаче ответ симметричен, поэтому ошибку не видно. В варианте с препятствиями она сразу вылезет в виде выхода за границы.

Как рассказывать на интервью

Задача входит в Blind 75, поэтому её часто решают при подготовке, и сама по себе она вряд ли кого-то удивит. Интересно здесь другое: у неё три уровня решения, и интервьюер видит, на каком вы остановитесь. Рабочий порядок такой:

1. Назовите рекуррентную формулу и объясните, почему складываем, а не, например, берём максимум.
2. Напишите таблицу, прогоните руками на $3 \times 2$.
3. Заметьте вслух, что нужна только предыдущая строка, и сожмите память.
4. Скажите про формулу через сочетания. Если есть время, напишите цикл и объясните, почему деление целочисленное.
5. Сами спросите, не появятся ли препятствия, и объясните, почему тогда возвращаетесь к ДП.

Пункт 5 — самый полезный: вы показываете, что понимаете границы применимости формулы, а не просто знаете её. Как проговаривать такие рассуждения, есть в статье про мышление вслух на интервью.

Что запомнить

• В клетку приходят сверху или слева, отсюда dp[i][j] = dp[i-1][j] + dp[i][j-1].
• Для сжатия хватает одной строки по короткой стороне: время $O(m \cdot n)$, память $O(\min(m, n))$. Обход слева направо.
• Путь — это выбор позиций шагов вниз, поэтому ответ равен $\binom{m+n-2}{m-1}$. Считается за $O(\min(m, n))$, сначала умножение, потом деление.
• С препятствиями формула больше не работает, а ДП работает: занятая клетка равна нулю, и никаких предзаполненных единиц.
• Ходы в четыре стороны убивают ДП по клеткам: появляются циклы.

Закрепить можно прямо на сайте: задача Уникальные пути принимает решения на Python, JavaScript и Java.