Начните в левом верхнем углу сетки с количеством ячеек rows на columns. Передвигайтесь только по рёбрам ячеек: на каждом шаге либо на одну ячейку вправо, либо на одну ячейку вниз, пока не достигнете правого нижнего угла. Посчитайте количество различных последовательностей ходов. В сетке нет препятствий.
Для сетки с 2 строками и 3 столбцами потребуется ровно 2 движения вниз и 3 движения вправо.
Реализуйте функцию lattice_paths(rows, columns).
Ввод
rows: Количество строк ячеек, не вершин.
columns: Количество столбцов ячеек, не вершин.
Вывод
Верните количество маршрутов из угла в угол.
Ограничения
0 ≤ rows, columns ≤ 30 и rows + columns ≤ 60. Ноль в одном из измерений означает единственный прямой маршрут. Для сетки 0 × 0 существует один пустой маршрут. Все значения помещаются в знаковый 64-битный тип.
Примеры
Ввод:
rows = 2
columns = 3
Ожидаемый вывод:
expected = 10Ввод:
long long rows = 2;
long long columns = 3;
Ожидаемый вывод:
long long expected = 10;Ввод:
long rows = 2;
long columns = 3;
Ожидаемый вывод:
long expected = 10;Пояснение
Каждый маршрут состоит из пяти ходов. Выбирая, какие два из них будут вниз, получаем десять различных маршрутов.
Ввод:
rows = 0
columns = 4
Ожидаемый вывод:
expected = 1Ввод:
long long rows = 0;
long long columns = 4;
Ожидаемый вывод:
long long expected = 1;Ввод:
long rows = 0;
long columns = 4;
Ожидаемый вывод:
long expected = 1;Пояснение
Есть только один прямой маршрут из четырёх движений вправо.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Каждый маршрут — это просто порядок нужных шагов down и right.
Подсказка 2
Считайте, сколькими способами можно выбрать позиции одного типа шага среди всех шагов, вместо перебора путей по одному.
Подсказка 3
Учитывайте вырожденные сетки: если одна размерность равна нулю, есть ровно один прямой маршрут, а в сетке 0×0 тоже есть один пустой маршрут.
Ожидаемая сложность
время O(min(rows, columns)), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.