algorithm - 打印到达第n个楼梯的方法

我最近在一次采访中遇到了这个问题
有楼梯，站在底部的人想爬到顶部这个人可以一次爬一个楼梯或两个楼梯。
打印所有可能的方式，人可以到达顶部。
例如，n输出：

1 2 3 4
1 2 4
1 3 4
2 3 4
2 4

但我不能正确地编码。如何为此编写解决方案？

最佳答案

要打印方法数，您可以首先了解如何计算方法数，然后对其进行调整，使每个“计数”将打印而不是仅计数：

D(0) = 1
D(-1) = 0
D(i) = D(i-1) + D(i-2)

要将其调整为实际打印，您需要“记住”所做的选择，并遵循相同的逻辑。伪代码：

printWays(curr, n, soFar):
   if curr > n:
      return
   soFar.append(curr)
   if n == curr:
      print soFar
      soFar.removeLast()
      return
   printWays(curr+1,n,soFar)
   printWays(curr+2,n,soFar)
   soFar.removeLast()

想法是：
sofar是您当前执行的一系列步骤。
curr是当前的步骤。
n是您需要到达的最后一个楼梯。
在每一点上，你要么爬一级楼梯，要么爬两级楼梯。两个选项都选中。