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

面试中给了我以下问题:



例如:

N = 3

Output :
1 1 1
1 2
2 1

面试时，我只是说要使用动态编程。



但是，在采访中，我没有为此编写很好的代码。您将如何为该问题编写解决方案？

的确的感谢!

最佳答案

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

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

它不是真正的代码，更多是伪代码，但是它应该可以使您有所了解。