寻找下楼梯的所有路径？ [英] Finding all paths down stairs?

问题描述

我得到了下面的问题，在接受记者采访时：

I was given the following problem in an interview:

由于有N个楼梯，你可以走了1个或2个步骤各一次。输出所有可能的方式，你从底部到顶部。

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

在采访中，我只是说使用动态规划。

When interviewing, I just said to use dynamic programming.

S（N）= S（N-1）1或S（N）= S（N-1）2

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

不过，在采访中，我没有写很好code这一点。你将如何code了一个解决这个问题？

However, during the interview, I didn't write very good code for this. How would you code up a solution to this problem?

感谢哉！

推荐答案

您可以概括您的递归函数也采取已经作出的动作。

You can generalize your recursive function to also take already made moves.

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));
    }
}

这不是真正的code，更多的是一种伪code，但它应该给你一个想法。

It's not really the code, more of a pseudocode, but it should give you an idea.

这篇关于寻找下楼梯的所有路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！