c++ - 找到所有下楼梯的路径？

Question

我在面试中遇到了以下问题:

Given a staircase with N steps, you can go up with 1 or 2 steps each time. Output all possible way you go from bottom to top.

例如:

N = 3

Output :
1 1 1
1 2
2 1

面试的时候，我只是说要使用动态规划。

S(n) = S(n-1) +1 or S(n) = S(n-1) +2

然而，在采访中，我并没有为此写出非常好的代码。您将如何编写解决此问题的代码？

非常感谢!

Answer 1

我不会为你编写代码(因为这是一个很好的练习)，但这是一个经典的动态规划问题。你在重复的正确轨道上；这是真的

S(0) = 1

因为如果你在楼梯的底部，那么只有一种方法可以做到这一点。我们也有这个

S(1) = 1

因为如果你高了一步，你唯一的选择就是往下走一步，此时你就处于底部。

从那里，很容易找到解决方案数量的递归。如果您考虑一下，您采取的任何步骤序列要么以一小步作为最后一步，要么以一大步作为最后一步。在第一种情况下，n - 1 个楼梯的 S(n - 1) 个解中的每一个都可以通过多走一步扩展为一个解，而在第二种情况下，n 个楼梯的每个 S(n - 2) 个解- 2个楼梯案例可以通过两个步骤扩展成一个解决方案。这给出了复发

S(n) = S(n - 2) + S(n - 1)

请注意，要计算 S(n)，您只需要访问 S(n - 2) 和 S(n - 1)。这意味着您可以使用以下逻辑通过动态编程来解决这个问题:

1. 创建一个数组 S，其中包含 n + 1 个元素，索引为 0、1、2、...、n。
2. 设置S[0] = S[1] = 1
3. 对于从 2 到 n(含)的 i，设置 S[i] = S[i - 1] + S[i - 2]。
4. 返回S[n]。

这个算法的运行时间是一个漂亮的 O(n) 与 O(n) 内存使用。

但是，可以做得比这更好。特别是，让我们看一下序列的前几项，它们是

 S(0) = 1
 S(1) = 1
 S(2) = 2
 S(3) = 3
 S(4) = 5

这看起来很像斐波那契数列，实际上你也许可以看到

 S(0) = F(1)
 S(1) = F(2)
 S(2) = F(3)
 S(3) = F(4)
 S(4) = F(5)

这表明，一般来说，S(n) = F(n + 1)。我们实际上可以通过对 n 的归纳来证明这一点，如下所示。

作为我们的基本案例，我们有这个

S(0) = 1 = F(1) = F(0 + 1)

和

S(1) = 1 = F(2) = F(1 + 1)

对于归纳步​​骤，我们得到了

S(n) = S(n - 2) + S(n - 1) = F(n - 1) + F(n) = F(n + 1)

瞧!我们已经按照斐波那契数列编写了这个系列。这很棒，因为可以在 O(1) 空间和 O(lg n) 时间计算斐波那契数。有很多方法可以做到这一点。一个人使用的事实是

F(n) = (1/√(5)) (Φⁿ + φⁿ)

这里，Φ是黄金比例，(1 + √5)/2(约1.6)，φ为1 - Φ，约-0.6。因为这第二项很快降为零，所以你可以通过计算得到第 n 个斐波那契数

(1/√(5)) Φⁿ

四舍五入。此外，您可以通过重复平方在 O(lg n) 时间内计算 Φⁿ。这个想法是我们可以使用这个很酷的递归:

x⁰ = 1

x²ⁿ = xⁿ * xⁿ

x^{2n + 1} = x * xⁿ * xⁿ

您可以使用快速归纳论证证明这在 O(lg n) 时间内终止，这意味着您可以使用 O(1) 空间和 O(lg n) 时间来解决这个问题，这基本上是 比 DP 解决方案好。

希望这会有所帮助!