C++ 爬楼梯递归问题？

Question

我们的目标是编写一个程序来计算和打印一个人一次走 1、2 或 3 级楼梯可以爬 n 级楼梯的所有不同方式。

我的递归算法有点问题:

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iomanip>

using namespace std;ctor< vector<int> > outer;
vector<int> inner;

vector< vector<int> > get_ways(int num_stairs) {
    // TODO: Return a vector of vectors of ints representing
    // the different combinations of ways to climb num_stairs
    // stairs, moving up either 1, 2, or 3 stairs at a time.
    if (num_stairs <= 0) {
        outer.push_back(inner);
        inner.clear();
    }
    if (num_stairs >= 1) {
        inner.push_back(1);
        get_ways(num_stairs-1);
    }
    if (num_stairs >= 2) {
        inner.push_back(2);
        get_ways(num_stairs-2);
    }
    if (num_stairs >= 3) {
        inner.push_back(3);
        get_ways(num_stairs-3);
    }

    return outer;
}

void display_ways(const vector< vector<int> > &ways) {
    for (unsigned int i = 0; i < ways.size(); i++) {
        cout << i+1 << ". " << "[";
        for (unsigned int j = 0; j < ways[i].size(); j++) {
            if (j != ways[i].size()-1)
                cout << ways[i][j] << ", ";
            else
                cout << ways[i][j];
        }
        cout << "]" << endl;
    }
}

错误示例:

get_ways(3)

预期输出 ->

1. [1, 1, 1]

2. [1, 2]

3. [2, 1]
4. [3]

实际输出->

1. [1, 1, 1]

//如果递归遇到多个 if 语句，算法不会打印前面的 1？

<强>2。 [2]

1. [2, 1]
2. [3]

非常感谢任何帮助!

Answer 1

实际代码应该是:

vector< vector<int> > get_ways(int num_stairs) {
    if (num_stairs <= 0) {
        outer.push_back(inner);
    }
    if (num_stairs >= 1) {
        inner.push_back(1);
        get_ways(num_stairs-1);
        inner.pop_back();
    }
    if (num_stairs >= 2) {
        inner.push_back(2);
        get_ways(num_stairs-2);
        inner.pop_back();
    }
    if (num_stairs >= 3) {
        inner.push_back(3);
        get_ways(num_stairs-3);
        inner.pop_back();
    }

    return outer;
}

为什么您的代码不正确？让我们跟踪函数堆栈和 vector inner:

Function stack              inner
get_way(3)                  []
  get_way(2)                [1]
    get_ways(1)             [1,1]
      get_ways(0)           [1,1,1] (*)
    get_ways(0)             [2]
    ....

在点 (*) 您清除了 inner 并且在 get_ways(2) 执行的下一步您将拥有 vector [2] 而不是 [1, 2]。因此，不是清除 inner，而是在完成递归调用后，您应该弹出在 inner 中最后压入的元素。这是您在回溯时应始终遵守的一条通用规则 - 始终将对象恢复到递归调用之前的状态。