# N個括號的匹配數

## 遞迴
想法:遍歷N個個位置,每次決定要選左括號還右括號,並滿足以下條件

1. 如果右括號等於n時代表結尾(左括號必大於等於右括號,此時兩個括號都等於n)
2. 如果左括號等於n時只能選擇右括號
3. 如果左括號等於右括號時只能選擇左括號,因為任何時候右括號都要小於等於左括號
4. 否則可選左括號和右括號

void rec(int l,int r){
    if(r==n){          //1.
        ans++;
        return;
    }else if(l==n){    //2.
        rec(l,r+1);
    }else if(l==r){    //3.
    	rec(l+1,r);
    }else{             //4.
        rec(l+1,r);
        rec(l,r+1);  
    }
}

缺點:O(2^n^),n=20時就超過百萬了,更大就會直接TLE,不能算到更大的數
## 公式

[卡特蘭數](https://oeis.org/A000108)

公式:

    2n!
-----------
 n!(n+1)!

有可能在算2n!的時候就溢位了,所以邊乘邊除可以避免,另外2n!和n!可以先約分

n=4

計算方式為乘上面第一個元素,除下面第一個元素,乘上面第二個元素,除下面第二個元素...
8*7*6*5
-------
1*2*3*4*5

ans=1
ans=ans*8/1*7/2*6/3*5/4*5/5

也可以把最後面的5約掉,但不會快多少就是了

long long formula(){
    long long ans=1;
    for(int i=2*n,j=1;i>n || j<=n+1;i--,j++){
        if(i>n) ans*=i;
        if(j<=n+1) ans/=j;
    }
    return ans;
}

這樣就可以算到30了,更大就要利用大數運算

## DP

定義dp[L][R]為取L個左括號和R個右括號的方法數,所以答案就是dp[L][R],每次可轉移的方法為在符合L>=R中,可取左括號或右括號,所以狀態轉移為:

dp[L][R]=dp[L-1][R]+dp[L][R-1]

可以把這表格看作是一個二維陣列,把橫坐標當作是L,縱座標當作是R,符合L>=R就代表在左下到右下斜線的右邊轉移,每個位置都符合L>=R,最大就是在斜線上,L==R,初始化時只需要注意L的邊界就好了,因為R不可能會比L(=0)大

void bottom_up(int n){
    vector<vector<int>> dp(n+1,vector<int>(n+1));
    for(int l=1;l<=n;l++) dp[l][0]=1;  //L數量的任意排列都是1

    for(int l=1;l<=n;l++){
        for(int r=1;r<=l;r++){
            dp[l][r]=dp[l-1][r]+dp[l][r-1];
        }
    }
    ans=dp[n][n];
}