algorithm - 在长度为 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

能否就如何解决此问题提供一些指导/链接？

Answer 1

它很可能可以使用组合方法而不是计算方法来解决。但由于您在 stackoverflow 上询问，我假设您需要一个计算解决方案。

定义以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]

对于给定的 K，我们可以针对 i=0..N 迭代计算 P[N, K, i] 的数组来自数组 P[N, K-1, i] for 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) 的 1 组成,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 时才优于迭代方法。