Количество способов сделать k шагов на пути длиной N

Question

У нас есть путь длины N. За один раз мы можем сделать только единичный шаг. Сколько способов мы можем сделать K шагов, оставаясь внутри пути. Изначально мы находимся на 0-й позиции. пример N =5

 |---|---|---|---|---|

 0   1   2   3   4   5

если к = 3, то мы движемся как -

0->1->2->1
0->1->0->1
0->1->2->3

Можете ли вы дать некоторые указания / ссылки о том, как подойти к этой проблеме?

Answer 1

Вероятно, это можно решить с помощью комбинаторных методов, а не вычислительных методов. Но так как вы спрашиваете о стековом потоке, я предполагаю, что вы хотите вычислительное решение.

Существует рекуррентное отношение, определяющее количество путей, заканчивающихся на i:

P[N, 0, i] = 1 if i==0 otherwise 0
P[N, K, i] = 0 if i<0 or i>N
P[N, K, i] = P[N, K-1, i-1] + P[N, K-1, i+1]

Мы можем итеративно вычислить массив P[N, K, i] за i=0..N для данного K из массива P[N, K-1, i] за i=0..N,

Вот некоторый код Python, который делает это. Он использует маленький трюк с дополнительным 0 в конце массива так, чтобы r[-1] а также r[N+1] оба равны нулю.

def paths(N, K):
    r = [1] + [0] * (N+1)
    for _ in xrange(K):
        r = [r[i-1]+r[i+1] for i in xrange(N+1)] + [0]
    return sum(r)

print paths(5, 3)

Это выполняется за время O(NK).

Другое (но связанное) решение состоит в том, чтобы M быть матрицей (N+1) by (N+1), состоящей из 1 в позициях (i+1,i) и (i,i+1) для i=0..N+1, и 0 в других местах - что 1 на субдиагональной и супердиагональной. затем M^K (то есть, M поднят к Kth power) содержит в позиции (i, j) количество путей из i в j в K шаги. Так sum(M^K[0,i] for i=0..N) общее количество всех путей, начинающихся с 0 длины K, Это выполняется за время O(N^3logK), поэтому лучше, чем итерационный метод, только если K намного больше, чем N,

Answer 2

Java реализация первого подхода в принятом ответе -

for (int i = 0; i <= K; i++) {
  for (int j = 1; j <= N; j++) {
    if (i > 0)
      dp1[i][j] = (dp1[i - 1][j - 1] + dp1[i - 1][j + 1]) % 1000000007;
    else
      dp1[i][j] = 1;
  }
}
System.out.println(dp1[K][N-1])

Сложность O(кн)

Реализация Java DP, она вычисляет ответы для всех начальных позиций и значений 1-N и 1-K -

for (int i = 0; i <= K; i++) {
  for (int j = 1; j <= N; j++) {
    for (int k = 1; k <= j; k++) {
      if (i > 0)
        dp[k][j][i] =
            (dp[k - 1][j][i - 1] + dp[k + 1][j][i - 1]) % 1000000007;
      else
        dp[k][j][i] = 1;
    }
  }
}
System.out.println(dp[1][5][3]);

О (КН ^2)