長さNのパスでkステップを実行する方法の数N

Question

長さNのパスがあります。一度に1単位ステップしか実行できません。パスの中に残っている間に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] 

我々は繰り返しi=0..Nのために、アレイP[N, K-1, i]から与えられたKためi=0..NためP[N, K, i]の配列を計算することができます。

これは、これを行う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）時間で実行されます。 （i + 1、i）および（i、i + 1）に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)は、長さが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）

ジャワ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）