Unique Paths (Уникальные пути)
Описание: Робот стоит в левом верхнем углу сетки m × n и может двигаться только вправо и вниз. Сколько существует различных путей до правого нижнего угла?
Пример 1:
Вход: m = 3, n = 7
Выход: 28
Объяснение: —
Пример 2:
Вход: m = 3, n = 2
Выход: 3
Объяснение: Вниз-вниз-вправо, вниз-вправо-вниз, вправо-вниз-вниз
Ограничения:
1 <= m, n <= 100
Рекомендуемая временная и пространственная сложность
Стремитесь к O(m · n) по времени и O(n) по памяти.
Подсказка 1
В любую клетку можно попасть только сверху или слева.
Подсказка 2
Значит количество путей в клетку равно сумме путей в клетку сверху и в клетку слева.
Подсказка 3
Для вычисления текущей строки нужна только предыдущая — храните одну строку.