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

本文介绍了打印到达第n个楼梯的方法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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.