Подсчет путей в рекурсивном вызове

Question

Проблемы Я работаю на это, из Крекинг кодирвоания Интервью:

«Ребенок работает вверх по лестнице с п шагами, и может перескакивать либо 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 вы должны установить пути = 0 перед циклом for. В противном случае это добавляет значения в глобальный экземпляр путей, и именно поэтому вы получаете неправильный ответ.

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 шага. С N-2 есть два способа: прыгать оба шага за один раз или прыгать 1 шаг и заканчивать оттуда. Теперь список «путей к завершению» выглядит следующим образом:

way = [1, 2, ...] 

Теперь, смотрите, что происходит с шагом N-3. Мы, наконец, есть 3 варианта:

1. Hop 1 шаг и есть 2 способа закончить
2. Hop 2 шага и имеют 1 способ закончить
3. Hop 3 шагов и будет сделано.

Это всего 2 + 1 + 1 или 4 способа закончить.

Это инициализирует наш алгоритм. Теперь для повторных отношений. Первоначальный список выглядит следующим образом:

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

Отныне мы не можем сделать ни одного прыжка на вершине. Вместо этого мы должны зависеть от трех шагов выше нас.Наш выбор от этапа NJ являются:

1. Hop 1 шаг и иметь путь [J-1] способов закончить
2. Hop 2 шага и имеют пути [J-2] способов закончить
3. Hop 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() 

Устранение рекурсии также вызывает меньше кадров, которые будут использоваться, и не останавливается с максимальной рекурсии.