計數路徑

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）中使用動態編程。並更有效地使用矩陣冪（logN）。

Answer 2

最重要的是，意識到你不必確定這些序列：你只需要對它們進行計數。例如，只有一種方法可以從步驟N-1完成：跳一步。從N-2開始，有兩種方法：一次跳兩步，或者跳1步並從那裏完成。我們的「完成方式」列表現在看起來像這樣，反向工作：

way = [1, 2, ...] 

現在，看看步驟N-3會發生什麼。我們終於有3種選擇：

1. 合1步，並有2種方式來完成
2. 合2步驟，必須完成
3. 跳三步並做1路。

這是總共2 + 1 + 1或4種方式完成。

初始化我們的算法。現在是重現關係。最初的列表看起來是這樣的：

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

從這裏開始，我們無法將單跳躍到頂端。相反，我們必須依靠我們上面的三個步驟。我們從步驟NJ的選擇是：

1. 合1個步驟和具有方式[J-1]方式來完成
2. 合2個步驟和具有方式[J-2]方式來完成
3. 合3個步驟，並且具有方式[J-3]方式完成

因此，對於所有的j> = 3：

way[j] = way[j-1] + way[j-2] + way[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 

正如你所看到的，有沒有必要繼續路徑作爲唯一的剩餘長度事項。

---

@ Prune的答案有更好的算法。在這裏它被實現：

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() 

消除遞歸也導致使用較少的幀，並不停止與最大遞歸。