在长度为 N 的路径上采取 k 步的方法数

Question

我们有一条长度为N的路径，一次只能走一个单位步。在保持在路径内的同时，我们可以采取多少种方式进行 K 步。最初我们在第 0 个位置。示例 N =5

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

 0   1   2   3   4   5

如果 k = 3 那么我们移动 -

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

能否就如何解决此问题提供一些 directions/links 信息？

Answer 1

它很可能可以使用组合方法而不是计算方法来解决。但是既然你在 Whosebug 上提问，我假设你想要一个计算解决方案。

有一个递归关系定义了以 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]

我们可以从 i=0..N 的数组 P[N, K-1, i] 中迭代计算给定 K 的 P[N, K, 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) x (N+1) 矩阵，由位置 (i+1,i) 和 (i, i+1) 对于 i=0..N+1，而 0 在别处——也就是说，1 在次对角线上和上对角线上。然后 M^K（即 M 的 K 次方）在位置 (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(KN)

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]);

O(KN^2)

在长度为 N 的路径上采取 k 步的方法数

Number of ways to take k steps on a path of length N

algorithm

combinatorics