階段の飛行を横断する別の方法

Question

私は以下のためにpythonでコードを書こうとしています：階段はn個あります。私は、階段1から階段nに達するさまざまな方法（総数の総数ではなく）を表示したいと思います。ここでのキャッチは、一度にm階段を超えることはできません。助けてください。注：mとnはユーザーによって入力されます。 次のコードは、方法の合計数を表示します。しかし、すべての異なる方法がありません何：

# A program to count the number of ways to reach n'th stair 


# Recursive function used by countWays 
def countWaysUtil(n,m): 
    if n <= 1: 
     return n 
    res = 0 
    i = 1 
    while i<=m and i<=n: 
     res = res + countWaysUtil(n-i, m) 
     i = i + 1 
    return res 

# Returns number of ways to reach s'th stair  
def countWays(s,m): 
    return countWaysUtil(s+1, m) 



# Driver program 

s,m = 4,2 
print "Number of ways =",countWays(s, m) 

Answer 1

これは、あなたがf(n) = f(n-1) + ... + f(n-m)を持っている代わりにf(n) = f(n-1) + f(n-2)除いて、一般Fibonacciシーケンスの一種のようです。あなたのコードはうまくいくはずですが、大規模な再帰はnの大きな値（非常に複雑で、私が間違っていなければO(m^n)の順番で）を提供します。この種の問題を解決する鍵は、リストの下位の入力値の結果を暗記することです：

def ways_up_stairs(n, m): 
    ways = [1] + [None] * n 
    for i in range(1, n+1): 
     ways[i] = sum(ways[max(0, i-m):i]) 
    return ways[n] 

いくつかの例入力と出力：

print(ways_up_stairs(4,2)) # 5 
print(ways_up_stairs(4,3)) # 7 
print(ways_up_stairs(4,4)) # 8 

あなたは実際のステップ・シーケンスがしたい場合は、和は、あなたが簡単にネストされたリストの内包表記を使用して、それに応じてコードを適応させることができません：あなたは、それは例えばあるとして、コードを少し適応する必要がある場合があります

def ways_up_stairs(n, m): 
    ways = [[(0,)]] + [None] * n 
    for i in range(1, n+1): 
     ways[i] = [w + (i,) for ws in ways[max(0, i-m):i] for w in ws] 
    return ways[n] 

print(ways_up_stairs(4,2)) 
# [(0, 2, 4), (0, 1, 2, 4), (0, 1, 3, 4), (0, 2, 3, 4), (0, 1, 2, 3, 4)] 

注意「mステップまでスキップする」とは、1..mまたは1..m+1のステップを取ることができることを意味しますが、一部の入力に対して期待される結果が得られた場合は、これらの「一回限りの」適応を容易にする必要があります。