Количество трасс в сетке с несколькими контрольно-пропускными пунктами

Question

Данная сетка размера N X N. Его нижняя левая точка - (0,0), а верхний правый - (N-1,N-1).

Мы можем пересекать сетку в верхнем или правом направлении. Нам нужно найти количество способов передвижения с нижней левой до верхней правой точки. Есть некоторые контрольно-пропускные пункты, которые мы должны посетить на каждом пути. Существует хотя бы один допустимый путь.

Пример: Пусть N=5 и мы имеем 1 контрольно-пропускной пункт на (2,2) то здесь ответ 36.

Примечание: мне нужно учитывать только допустимые пути и не беспокоить их поиск.

Что может быть эффективным способом их подсчета?

Answer 1

вы должны знать две вещи:

1. Rule of product: это означает, что число путей от начала до конца является равное число путей от начала до средней точки * число путей от средней точки до конца.

2. C (R, R + U) (R это число ваших правильных ходов и U это число до ходов это означает, что если вы хотите, чтобы перейти от (a,b) к (c,d) затем R = c-a и U = d-b и C(R,R+U) = (R+U)!/R!U!) является ответом на то, как много способов от нижнего левого к верхнему праву в сетке.

Пример в вашем примере из моего второго правила мы имеем:

количество ходов от (0,0) до (2,2), потому что после двух правого хода от 0 вы достигнете 2 и после того, как два движения вверх от 0 вы достигнете 2 поэтому R=2 и U=2 поэтому C(2,2+2) = C(2,4) = 4!/2!2! = 6.И делать то же самое для R и U числа ходов от (2,2) до (4,4) является C(2,2+2) = C(2,4) = 4!/2!2! = 6

и из первого правила имеет число всех возможных ходов: 6 * 6 = 36

Answer 2

Использования динамическое программирование:

dp[k, i, j] = number of paths from checkpoint k to (i, j) 

dp[k, i, j] = dp[k, i - 1, j] +  top 
       dp[k, i, j - 1]   right 

Ответ является продуктом dp значений между контрольно-пропускными пунктами.

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

Answer 3

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

Решение здесь будет:

1. Сортировка точки от источника до пункта назначения.

Пример: Если начальная точка находится [0,0] конечная точка [10,10], а промежуточные пункты быть [5,6], [2,4] & [8,8], то отсортировано (включая источник и место назначения) были бы [0,0], [2,4], [5,6], [8,8], [10,10] в матрице 11X11

2. Найти количество путей (предпочтительно с использованием DP) от источника к следующему месту назначения. (Для того, отсортированных точек)

В приведенном выше примере, число путей, которые должны быть рассчитаны бы между следующими пунктами:

[0,0] до [2,4]

[2,4] до [5,6]

[5,6] на [8,8]

[8,8] на [10,10]

3. Найти е произведение всех вышеуказанных 4 суб путей

Вот это

Вот solution для нахождения числа путей (см DP подход) от источника и назначения. Вам не нужно передавать матрицу в качестве аргумента, поскольку это просто не нужно. Нужны только исходные и целевые точки в виде [x, y] [X, Y]. Другая часть (сортировка точек и умножение) должна выполняться, как объяснялось выше, кроме кода, содержащегося в ссылке.