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

Question

最近面试遇到这个问题

有n个楼梯，站在底部的人想爬到顶部。这个人一次可以爬 1 个楼梯或 2 个楼梯。

打印出人们到达顶部的所有可能方式。

例如，n=4 输出:

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

但我无法正确编码。如何为此编写解决方案？

Answer 1

要打印路数，您可以先了解如何计算路数，并调整它以便打印每个“计数”，而不仅仅是计数:

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

思路是:

• 到目前为止是您当前执行的一系列步骤。
• curr 是您当前所在的步骤。
• n 是您需要到达的最后一个楼梯。
• 在每个点，您要么爬一个楼梯，要么爬两个楼梯。您检查两个选项。