有效括号数目递推法

问题描述

给定一组包含n对括号的序列，需要计算能够形成有效括号组合的总方案数。

思路

合法括号序列的最终字符必定为右括号，因此其结构形式可表示为A(B)。其中，A与B分别代表两个合法的括号序列，二者均可为空。为确保所有可能性均被涵盖，需依次遍历A与B的取值范围：（0，n -1）、…、（k，n - k - 1）、（n - 1，0）。

由此可得递推公式为：

当n取值为0的情况下，唯一可生成的序列为不包含任何元素的空序列。

复杂度

该算法的核心递推式执行次数为1加2加3加…加n，由此可得其时间复杂度为O(n²)。

代码

    #include <bits/stdc++.h>
    using namespace std;
    const int MOD = 998244353;
    int n, f[100010];
    
    int main() {
    cin >> n;
    f[0] = 1; // 初始条件
    for( int i = 1; i <= n; ++i ) { //