Количество способов обхода двумерного массива сверху слева направо снизу

Наткнулся на этот вопрос в элементах интервью по программированию (16.3). Я следую решению DP, но они также дают это аналитическое решение, которого нет у меня. Постановка проблемы:

Напишите программу, которая подсчитывает, сколько способов можно пройти из левого верхнего угла в правый нижний в двумерном массиве.

Аналитическое решение:

Учитывая тот факт, что каждый путь от (0, 0) до (n-1, m-1) представляет собой последовательность из m-1 шагов по горизонтали и n-1 шагов по вертикали, должно быть (n+m-2) Выберите ( n-1) = (n+m-2)!/((n-1)!(m-1)! таких путей.

Я понимаю, что равенство просто применяет формулу n Choose k, и я вижу, что n + m-2 = (n - 1) + (m - 1). Но я действительно не знаю, почему количество путей равно (n - 1) + (m - 1) Выберите (n - 1) для начала? Из общего количества ходов выбираем набор вертикальных? Почему такое количество путей?


multidimensional-array combinations
person connorwstein    schedule 28.03.2018    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Поскольку каждый путь состоит из m-1 шагов по горизонтали и n-1 шагов по вертикали, всего на каждом пути есть m+n-2 шагов. Чтобы выбрать конкретный путь, вы можете определить либо вертикальные, либо горизонтальные шаги. Допустим, вы определили все вертикальные шаги (то есть n-1 из них). После того, как они определены, для остальных шагов (горизонтальных) нет фактического выбора - есть только одна единственная возможность для каждого горизонтального шага (который устанавливает связь между соседними вертикальными шагами). Следовательно, выбор n-1 из m+n-2 определяет единственный допустимый путь. А общее количество путей будет количеством возможностей выбрать n-1 из m+n-2 (того же результата можно добиться, выбрав m-1 вместо n-1).

См. пример ниже:

введите здесь описание изображения

Допустим, вы выбрали вертикальные шаги (красные) — после того, как это будет сделано, будет только один вариант для каждого горизонтального шага (синие). В противном случае путь будет прерывистым и в результате недействительным.

person SomeWittyUsername    schedule 17.04.2018
comment
Ах да, выбирая один набор шагов (вертикальный или горизонтальный), другой становится фиксированным. Спасибо. - person connorwstein; 18.04.2018

arrow_upward
0
arrow_downward

Я думаю, что постановка задачи не завершена, аналитическое решение работает только тогда, когда на каждом шаге вы можете идти только вверх или вправо, если мы можем идти только вверх или вправо, тогда нам нужен (n - 1) + (m - 1) шаг, чтобы достичь верхнего левого в (n - 1) шаге этих шагов мы должны идти направо, а в других мы должны подняться, ответ задачи будет ((n + m - 2) choose (n - 1)) or ((n + m - 2) choose (m - 1))

person Mani Hajimehdi    schedule 17.04.2018