在長度爲N的路徑上採取k個步驟的方法數量

Question

我們有一個長度爲N的路徑。一次只能採取單位步驟。我們可以採取多少種方式，同時保留在路徑中。最初我們處於第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] 

我們可以反覆從陣列P[N, K-1, i]計算的P[N, K, i]的數組i=0..N對於一個給定的Ki=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）時間。 （1 + 1）和（i，i + 1）組成的（N + 1）矩陣組成的（N + 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)是從長度爲K的0開始的所有路徑的總數。這在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）