は、私が働いている

Question

問題はコーディングインタビューをクラッキングから、このある再帰呼び出しのパスを数える：

「子供は、n個のステップに階段を実行している、と1つのステップ、2つのステップのいずれかをホップすることができます、 または一度に3ステップ。 子供が階段を上っていくことができる方法をいくつ計算するかの方法を実装してください。

C++からは、参照として渡すことができますが、Pythonではできません。私はまた、成功をもたらすステップシーケンスを追跡しようとしています。私はこのように私のコードを書いている：

def __calculatePaths(currPathLength, paths, currSeries): 
    if currPathLength == 0: 
    print "successful series is", currSeries 
    return 1 
    elif currPathLength < 0: return 0 

    for i in range(1, 4): 
    newSeries = list(currSeries) # make new series to track steps 
    newSeries.append(i) 
    paths += __calculatePaths(currPathLength - i, paths, newSeries) 
    return paths 

def calculatePaths(pathLength): 
    paths = __calculatePaths(pathLength, 0, []) 
    return paths 

if __name__ == '__main__': 
    calculatePaths(3) 

この呼び出しの出力は次のとおりです。

successful series is [1, 1, 1] 
successful series is [1, 2] 
successful series is [2, 1] 
successful series is [3] 
6 

私のプログラムは、正しいパスシーケンスが、パスの間違った番号を取得するので、私は混乱しています。パスを増やすにはどうすればいいですか？私は、グローバル変数なしでこれを行う方法を知っていますが、私はそれを使用せずにそれを把握することはできません。ありがとうございました！

Answer 1

__calculatePaths関数では、forループの前にpaths = 0を設定する必要があります。それ以外の場合は、パスのグローバルインスタンスに値を追加するので、間違った答えが得られます。

def __calculatePaths(currPathLength, paths, currSeries): 
    if currPathLength == 0: 
    print "successful series is", currSeries 
    return 1 
    elif currPathLength < 0: return 0 
    paths = 0 
    for i in range(1, 4): 
    newSeries = list(currSeries) # make new series to track steps 
    newSeries.append(i) 
    paths += __calculatePaths(currPathLength - i, paths, newSeries) 
    return paths 

def calculatePaths(pathLength): 
    paths = __calculatePaths(pathLength, 0, []) 
    return paths 

if __name__ == '__main__': 
    calculatePaths(3) 

多くの方法を効率的に取得できます。 O（N）で動的プログラミングを使用することによって。さらに、行列のべき乗剰余演算O（logN）を使用すると効率的です。

Answer 2

これらの配列を決定する必要はないことを理解しておく必要があります。たとえば、ステップN-1から終了する方法は1つだけです。ホップ1ステップです。 N-2からは、2つの方法があります：一度に両方のステップをホップするか、そこから1ステップ進んで終了します。

way = [1, 2, ...] 

ここで、手順N-3で何が起こるかを見てください。私たちは、最終的には3つの選択肢があります。

1. ホップ1つのステップをして
2. ホップ2つのステップを完了して
3. ホップ3つの段階を終了する1つの方法を持ってして行うことには2つの方法があります。

合計で2 + 1 + 1または4通りあります。

アルゴリズムを初期化します。今度は再発関係です。最初のリストは次のようになります。

way = [1, 2, 4, ...] 

ここから上にシングルホップを作成することはできません。代わりに、我々は私たちの上の3つのステップに依存しなければなりません。

1. ホップ1つのステップと方法[J-1]
2. ホップ2つのステップを完了し、方法[J-2]
を終了するの方法を持っている方法があります。ステップNJから私たちの選択肢があります
3. ホップ3つのステップと全てのj> = 3のために、このよう

を終了する方法方法[J-3]を有する：

を

これは、O（N）時間の解を提供します。

Answer 3

これはあなたのソリューション使用して、賢明なコンピューティングそれを行うための最も効率的な方法でなければなりません：あなたが見ることができるように

from collections import deque 


def calculate_paths(length): 
    count = 0 # Global count 

    def calcuate(remaining_length): 
     # 0 means success 
     # 1 means only 1 option is available (hop 1) 
     if remaining_length < 2: 
      nonlocal count # Refer to outer count 
      count += 1 
      return 

     # Calculates, removing the length already passed. 
     # For 1...4 or remaining_length+1 if it's less than 4. 
     # deque(, maxlen=0) is the fastest way of consuming an iterator 
     # without also keeping it's data. This is the most efficient both 
     # memory-wise and clock-wise 
     deque((calcuate(remaining_length-i) 
       for i in range(1, min(4, remaining_length+1))), maxlen=0) 

    calcuate(length) 
    return count 

>>> calculate_paths(2) 
2 
>>> calculate_paths(3) 
4 
>>> calculate_paths(4) 
7 

を、唯一の残りの長さの問題としてパスを維持する必要はありません。

---

@プルーンの答えがより良いアルゴリズムを持っています。ここでは実装されている：再帰を排除

def calculate_paths(length): 
    results = deque((1, 2, 4), maxlen=3) 
    if length <= 3: 
     return results[length-1] 

    for i in range(3, length): 
     results.append(sum(results)) 

    return results.pop() 

も少ないフレームが使用されるようになり、そして最大の再帰を停止しません。