python - 计算递归调用中的路径

Question

我正在解决的问题是这个，来自破解编码面试:

“一个 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

最重要的是，认识到您不必确定这些序列:您只需要对它们进行计数。例如，从步骤 N-1 开始只有一种方法:跳 1 步骤。从 N-2 开始，有两种方法:同时跳两个步骤，或者跳 1 个步骤并从那里完成。我们的“完成方法”列表现在看起来像这样，向后推算:

way = [1, 2, ...]

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

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

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

这会初始化我们的算法。现在来说说递归关系。初始列表如下所示:

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

从现在开始，我们再也不能跳到山顶了。相反，我们必须依赖上面的三个步骤。我们从步骤 N-J 中的选择是:

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)时间内为您提供解决方案。