计算递归调用中的路径

Question

我正在处理的问题是这个，来自 Cracking the Coding Interview：

"A child 正在运行爬 n 步楼梯，可以跳 1 步、2 步、或一次 3 个步骤。实现一个方法来计算有多少种可能的方式 child 可以运行上楼梯。"

来自 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 步。从 N-2 开始，有两种方法：一次跳两步，或跳 1 步并从那里完成。我们的 "ways to finish" 列表现在看起来像这样，向后工作：

way = [1, 2, ...]

现在，看看第 N-3 步会发生什么。我们最终有3个选择：

跳 1 步，有 2 种方法可以完成
跳 2 步，有 1 种方法可以完成
跳 3 步即可完成。

总共有 2+1+1，或 4 种方法可以完成。

这将初始化我们的算法。现在是递归关系。初始列表如下所示：

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

从现在开始，我们不能一步登顶了。相反，我们必须依赖于我们上面的三个步骤。我们从第 N 步到第 J 步的选择是：

跳 1 步，有 种方式[J-1] 种方式完成
跳 2 步，有 种方式[J-2] 种方式完成
跳 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()

消除递归也会导致使用更少的帧，并且不会因最大递归而停止。

计算递归调用中的路径

Counting paths in a recursive call

python

recursion

counter