括号合法匹配数问题

#include<iostream>
using namespace std;
int n;//门数*2,这里为便于编程默认n为偶数
int k;//k种括号
//dg函数返回值表示在第door对括号保持flag状态和noclose个未闭合门数情况下第door+1对括号的位置的可能（主要判断左括号）
int dg(int door,int flag, int noclose)//door 是门的序号，flag为1表示立即闭合，为0表示不立即闭合,noclose是包括此门在内的未闭合门数
{
    if (2 * (door + 1) == n)//相当于一棵树如果从根走到叶子则为一种方法，而对于倒数第二个括号无论是否立即闭合，它的下一对括号（即最后一对括号）的位置都是唯一确定的
        return 1;
    int sum = 0;
    for (int i = 0; i <= noclose; i++)
    {
        sum += dg(door + 1, 1, i);
    }
    return dg(door + 1, 0,noclose+1) + sum;
}
int main()
{
    cin >> n;
    cin >> k;
    int x = n / 2;
    int num = pow(k, x);
    if (n == 2)
    {
        cout << num;
        return 0;
    }
    int cnt = dg(1, 1,0) + dg(1, 0,1);
    int ans = num * cnt;
    cout << ans;
    return 0;
}

题目是n位（n/2对括号，n为偶数），求合法括号安排数。 我的思想： 第x对括号对第x+1对括号的左括号位置的影响仅在于第x对括号是否立即闭合： 1.如果非立即闭合，则第x+1对括号的左括号位置唯一确定，右括号位置可能性与第x+1对括号是否立即闭合有关，这就是递归了 2.如果立即闭合，则第x+1对括号的左括号位置可能性有1+noclose种（noclose是当前未闭合括号数），对于每种，其右括号位置都与其是否立即闭合有关，这又是递归

#include<iostream>
using namespace std;
int n;//门数*2,这里为便于编程默认n为偶数
int k;//k种括号
int dg(int lnum,int rnum)//左括号有lnum个，右括号有rnum个的情况下的合法匹配数
{
    int x=0, y=0;
    if (lnum == n / 2 && rnum == n / 2)
        return 1;
    if (lnum < n/2)//优先加左括号
        x = dg(lnum + 1, rnum);//x是加左括号的合法匹配数
    if (lnum > rnum)//再加右括号
        y = dg(lnum, rnum + 1);//y是加右括号的合法匹配数（与上面加左括号不是互斥关系）
    return x + y;

}
int main()
{
    cin >> n;
    cin >> k;
    int x = n / 2;
    int num = pow(k, x);
    if (n == 2)
    {
        cout << num;
        return 0;
    }
    int cnt = dg(0,0);
    int ans = num * cnt;
    cout << ans;
    return 0;
}

上面这种是我看的一个博主的方法，感觉更简便。 思想： 记录当前的左括号个数和右括号个数，左括号数小于总括号数时加左括号，然后如果左括号数大于右括号数则加右括号**（注意加括号的顺序：先递归加左括号，再递归加右括号）** 左括号数==右括号数==总括号数时为1个合法匹配，返回1。 这个思想也是从根逐渐加左右括号直至成为合法匹配，然后统计这样的情况数量。