找到楼梯下的所有路径？

Question

我在接受采访时遇到了以下问题:

给定一个有N个台阶的楼梯,每次可以进行1步或2步.输出从下到上的所有可能方式.

例如:

N = 3

Output :
1 1 1
1 2
2 1

在面试时,我只是说使用动态编程.

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

但是,在采访中,我没有为此编写非常好的代码.你会如何编写这个问题的解决方案？

谢谢!

Answer 1

我不会为你编写代码(因为这是一个很好的练习),但这是一个经典的动态编程问题.随着复发,你走在正确的轨道上; 这是真的

S(0)= 1

因为如果你在楼梯的底部,只有一种方法可以做到这一点.我们也有

S(1)= 1

因为如果你只有一步之遥,你唯一的选择是向下一步,此时你就在底部.

从那里,很容易找到解决方案数量的重现.如果您考虑一下,您采取的任何步骤都可以采取一小步作为最后一步,也可以采取一个大步骤作为最后一步.在第一种情况下,n - 1阶梯的每个S(n - 1)解可以通过再迈一步来扩展到解,而在第二种情况下,每个S(n - 2)解到n - 通过两个步骤,可以将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. 对于i从2到n,包括,设置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

这看起来很像Fibonacci序列,事实上你可能会看到它

 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)

瞧!我们用Fibonacci数字来编写这个系列.这很好,因为可以在O(1)空间和O(lg n)时间内计算Fibonacci数.有很多方法可以做到这一点.一个人使用这个事实

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的溶液更好.

希望这可以帮助!

Answer 2

您可以概括您的递归函数,也可以采取已经进行的移动.

void steps(n, alreadyTakenSteps) {
    if (n == 0) {
        print already taken steps
    }
    if (n >= 1) {
        steps(n - 1, alreadyTakenSteps.append(1));
    }
    if (n >= 2) {
        steps(n - 2, alreadyTakenSteps.append(2));
    }
}

它不是真正的代码,更像是伪代码,但它应该给你一个想法.

Answer 3

您的解决方案听起来不错。

S(n):
    If n = 1 return {1}
    If n = 2 return {2, (1,1)}
    Return S(n-1)x{1} U S(n-2)x{2}

（U 是并集，x 是笛卡尔积）

记住这一点是微不足道的，并且会成功O(Fib(n))。