題目描述：
/**
合法的括號匹配序列被定義為:
1. 空串""是合法的括號序列
2. 如果"X"和"Y"是合法的序列,那么"XY"也是一個合法的括號序列
3. 如果"X"是一個合法的序列,那么"(X)"也是一個合法的括號序列
4. 每個合法的括號序列都可以由上面的規(guī)則生成
例如"", "()", "()()()", "(()())", "(((())))"都是合法的墨坚。
東東現(xiàn)在有一個合法的括號序列s,
一次移除操作分為兩步:
1. 移除序列s中第一個左括號
2. 移除序列s中任意一個右括號.保證操作之后s還是一個合法的括號序列
東東現(xiàn)在想知道使用上述的移除操作有多少種方案可以把序列s變?yōu)榭?如果兩個方案中有一次移除操作移除的是不同的右括號就認(rèn)為是不同的方案秧饮。
例如: s = "()()()()()",輸出1, 因為每次都只能選擇被移除的左括號所相鄰的右括號.
s = "(((())))",輸出24, 第一次有4種情況, 第二次有3種情況, ... ,依次類推, 4 * 3 * 2 * 1 = 24
輸入描述:
輸入包括一行,一個合法的括號序列s,序列長度length(2 ≤ length ≤ 20).
輸出描述:
輸出一個整數(shù),表示方案數(shù)
輸入例子1:
(((())))
輸出例子1:
24
*/
思路如下：
方案一:
觀察題目給出的例子計算：
設(shè)str為k個(連續(xù)開頭，且str合法
那么str
一定是 ((...()合法串)...合法串)
那么按著題目操作去掉第一個(,后面有k個)可以去掉
但是不能去掉合法串中的)否則就會非法
而且去掉k個后的)的新的串合法泽篮，而且是同樣性質(zhì)盗尸，都是k-1個(連續(xù)開頭的新串,
那么基于這種原理，那么就可以維護(hù)一個指針計算當(dāng)前最左端連續(xù)去掉的個數(shù)即可
方案二：
DFS時間最壞復(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;//刪除最左邊的一個(可以產(chǎn)生更多的left_cnt字串帽撑，再運(yùn)用乘法原理
left_cnt--;//刪除最左邊的一個
}
else{
return -1;
}
}
printf("%d", res);
return 0;
}
