打印到达第n个楼梯的方法 [英] Print ways to reach the n’th stair

问题描述

我最近在一次采访中遇到了这个问题

I recently encountered this problem in an interview

有 n 个楼梯，一个站在底部的人想要到达顶部.该人一次可以爬1步或2步.

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time.

打印人员可能到达顶端的所有可能方式.

Print all possible ways person can reach the top.

例如， n = 4 输出:

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

但是我无法对此进行正确编码.如何为此编写解决方案?

But I couldn't code this properly. How to code up solution for this?

推荐答案

要打印路数，您首先应该了解如何计算路数，并对其进行调整，以便将打印每个计数"，而不仅仅是计数:

To print the number of ways, you can first understand how to calculate the number of ways, and adjust it so each "count" will print instead of just count:

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

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

To adjust it to actual printing, you need to "remember" the choices you have made, and follow the same logic. Pseudo code:

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 是您需要到达的最后一个楼梯.
• 在每个点上，您要么爬一两个台阶.您选中了这两个选项.

• soFar is the current series of steps you did.
• curr is the current step you're at.
• n is the last stair you need to get to.
• At each point, you either climb one stair or two. You check both options.

这篇关于打印到达第n个楼梯的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！