栈的合法出栈序列个数：动态规划 C++ 代码实现

这是一个经典的问题，可以使用动态规划来解决。

假设栈中有 n 个元素，我们用 f[i][j] 表示当前栈中还剩 i 个元素，已经出栈了 j 个元素的情况下的合法出栈序列个数。那么我们可以得到以下状态转移方程：

当栈顶元素可以出栈时，f[i][j] = f[i-1][j-1] 当栈顶元素不可以出栈时，f[i][j] = f[i-1][j] + f[i][j-1]

其中，当栈顶元素可以出栈时，我们将栈顶元素出栈，同时 j+1，将问题转化为 i-1 个元素已经出栈了 j-1 个元素的情况下的合法出栈序列个数。

当栈顶元素不可以出栈时，我们只能将栈顶元素压入栈中，同时 i-1，将问题转化为 i-1 个元素已经出栈了 j 个元素的情况下的合法出栈序列个数，以及 i 个元素已经出栈了 j-1 个元素的情况下的合法出栈序列个数。

最终的答案就是 f[n][n]，即 n 个元素已经出栈了 n 个元素的情况下的合法出栈序列个数。

以下是简单的 C++ 代码实现：

#include <iostream>
using namespace std;

const int MAXN = 15;

int f[MAXN][MAXN];

int main() {
    int n;
    cin >> n;

    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                f[i][j] = f[i-1][j];
            } else {
                f[i][j] = f[i-1][j] + f[i][j-1];
            }
        }
    }

    cout << f[n][n] << endl;

    return 0;
}

注意，这里的代码只考虑了栈中所有元素都不相同的情况，如果栈中有相同元素的话，需要考虑相同元素的出现次数。