Unique Paths

Подумай о последнем ходе робота в нижнюю правую клетку. Он попал туда либо вниз из клетки сверху, либо вправо из клетки слева, но не обоими способами. Поэтому количество путей через сетку m × n равно количеству путей через сетку на одну строку короче, uniquePaths(m-1, n), плюс количеству путей через сетку на один столбец уже, uniquePaths(m, n-1).

Рекурсия останавливается на сетке с одной строкой или одним столбцом, где робот может двигаться только прямо, поэтому существует ровно 1 путь. Каждый путь заканчивается одним из двух ходов, так что каждый путь учитывается один раз, и итог верен.

Это медленно, потому что каждый путь заканчивается базовым случаем, который возвращает 1, поэтому количество вызовов не меньше самого ответа. Для сетки 17 × 17 требуется более 600 миллионов вызовов, а в тестах встречаются ответы, близкие к 1.6 × 10^9. Одни и те же сетки меньшего размера вычисляются много раз: (m-1, n-1) достигается от каждого из двух родительских состояний, а по мере продвижения вниз количество повторов растёт.

Рекурсия снова и снова обращается к одним и тем же ячейкам, а всего ячеек только m × n. Подсчитайте количество путей до каждой ячейки один раз в таком порядке, чтобы нужные ячейки всегда были готовы.

Состояние: paths[r][c] — количество путей от верхней левой ячейки до строки r, столбца c. Рекуррентное соотношение: paths[r][c] = paths[r-1][c] + paths[r][c-1] — количество путей, приходящих сверху, плюс количество путей, приходящих слева. Базовые случаи: до каждой ячейки в верхней строке и левом столбце ведёт 1 путь — прямая линия. Порядок: построчно, слева направо, чтобы ячейки сверху и слева были заполнены до того, как они понадобятся.

Для m = 3 и n = 4 строки будут такими: 1 1 1 1, затем 1 2 3 4, затем 1 3 6 10, и ответ — последняя ячейка, 10.

Теперь посмотрим, какие данные читает заполнение: только предыдущую строку и заполняемую строку. Поэтому храните одну строку. Перед обновлением row[c] в ней всё ещё содержится количество путей из предыдущей строки, а row[c-1] уже содержит новое количество путей слева, поэтому row[c] += row[c-1] — это всё рекуррентное соотношение. Время работы остаётся O(m × n), а объём памяти сокращается с O(m × n) до O(n).

Каждый путь состоит ровно из m-1 шагов вниз и n-1 шагов вправо — всего m+n-2 шагов в некотором порядке. Любой порядок образует допустимый путь: робот никогда не делает больше m-1 шагов вниз или n-1 шагов вправо, поэтому он не выходит за пределы сетки. Следовательно, путь — это то же самое, что выбор m-1 из m+n-2 шагов, направленных вниз, а ответом будет биномиальный коэффициент C(m+n-2, m-1).

Таблица из предыдущего подхода — это треугольник Паскаля, повёрнутый на бок, поэтому результаты совпадают. Чтобы вычислить коэффициент, не используя огромные факториалы, последовательно умножайте на каждый множитель. При N = m+n-2 и k = min(m, n)-1 умножайте на N-k+i, а затем делите на i для i от 1 до k. После шага i текущее значение равно C(N-k+i, i) — целому числу, поэтому каждое деление выполняется без остатка.

Для m = 3 и n = 4: N = 5, k = 2, и значение меняется так: 1 × 4 / 1 = 4, затем 4 × 5 / 2 = 10. Выбор по более короткой стороне ограничивает цикл 99 шагами. Произведение перед последним делением равно k, умноженному на ответ. Для сетки 17 × 17 это 16 × 601,080,390, то есть примерно 9.6 × 10^9 — больше, чем позволяет 32-битный диапазон, поэтому храните значение в 64-битном целом числе.