題目描述：

/**
合法的括號(hào)匹配序列被定義為:
1. 空串""是合法的括號(hào)序列
2. 如果"X"和"Y"是合法的序列,那么"XY"也是一個(gè)合法的括號(hào)序列
3. 如果"X"是一個(gè)合法的序列,那么"(X)"也是一個(gè)合法的括號(hào)序列
4. 每個(gè)合法的括號(hào)序列都可以由上面的規(guī)則生成
例如"", "()", "()()()", "(()())", "(((())))"都是合法的。
東東現(xiàn)在有一個(gè)合法的括號(hào)序列s,
一次移除操作分為兩步:
1. 移除序列s中第一個(gè)左括號(hào)
2. 移除序列s中任意一個(gè)右括號(hào).保證操作之后s還是一個(gè)合法的括號(hào)序列
東東現(xiàn)在想知道使用上述的移除操作有多少種方案可以把序列s變?yōu)榭?如果兩個(gè)方案中有一次移除操作移除的是不同的右括號(hào)就認(rèn)為是不同的方案。
例如: s = "()()()()()",輸出1, 因?yàn)槊看味贾荒苓x擇被移除的左括號(hào)所相鄰的右括號(hào).
s = "(((())))",輸出24, 第一次有4種情況, 第二次有3種情況, ... ,依次類推, 4 * 3 * 2 * 1 = 24
輸入描述:
輸入包括一行,一個(gè)合法的括號(hào)序列s,序列長(zhǎng)度length(2 ≤ length ≤ 20).
輸出描述:
輸出一個(gè)整數(shù),表示方案數(shù)
輸入例子1:
(((())))
輸出例子1:
24
*/

思路如下：

方案一:
觀察題目給出的例子計(jì)算：
設(shè)str為k個(gè)(連續(xù)開(kāi)頭，且str合法
那么str
一定是 ((...()合法串)...合法串)
那么按著題目操作去掉第一個(gè)(,后面有k個(gè))可以去掉
但是不能去掉合法串中的)否則就會(huì)非法
而且去掉k個(gè)后的)的新的串合法，而且是同樣性質(zhì)，都是k-1個(gè)(連續(xù)開(kāi)頭的新串,

那么基于這種原理，那么就可以維護(hù)一個(gè)指針計(jì)算當(dāng)前最左端連續(xù)去掉的個(gè)數(shù)即可

方案二：
DFS時(shí)間最壞復(fù)雜度O(len2^(len+1))
加上記憶化空間復(fù)雜度O(2^(len+1)len)

代碼如下：

#include<stdio.h>
#include<iostream>
#include<string>
#include<map>
 
using namespace std;
 
int main(){
    string str;
    cin>>str;
    int left_cnt=0, res=1;
    for(int i=0; i<str.size(); i++){
        if(str[i]=='('){
            left_cnt++;
        }
        else if(str[i]==')'){
            res*=left_cnt;//刪除最左邊的一個(gè)(可以產(chǎn)生更多的left_cnt字串，再運(yùn)用乘法原理
            left_cnt--;//刪除最左邊的一個(gè)
        }
        else{
            return -1;
        }
    }
    printf("%d", res);
    return 0;
}