プログラマ-右かっこの数

問題を見て点火式を作り、それからdp、dp[0]x?+dp[1]x?? + ... 見つけましたが、進展がなかったので、グーグルをいくつかしました.
カタラン数という点火方式で求められる問題だった.

たとえば、
C0 = 1
C1 = C0 x C0
C2 = C0 x C1 + C1 x C0
C3 = C0 x C2 + C1 x C1 + C2 x C0
こうなります.
なぜカタランの木なのか考えてみましょう
Aはn-k-1、Bはk個の正しい括弧の集合であり、この二つの括弧を以下の形式にまとめることができる.
C=(A)B(Cはn個の有効括弧の集合)
また、Aの位置では0、1、2...n-1、Bを逆にn-1、n-2...0までの純素であってもよく、カタラン数の性質を有する.
コードは以下の通りです.

// 카탈란수로 구현한 결과
#include <string>
#include <vector>

using namespace std;

int answer = 0;
int dp[20] = { 1 };
void catalan(int n) 
{
    int sum = 0;
    for(int i=0;i<n;i++) 
        sum += dp[i] * dp[n-i-1];
    dp[n] = sum;
}
int solution(int n) {
    
    for(int i=1; i<=n; i++) 
        catalan(i);
    answer = dp[n];
    
    return answer;
}

カタラン水で実施した結果

Catalan数で実現した後、他の人のコードがDFSになったのを見て、私はすぐに実現しました.
nからopenを外す人も多いですが、意味的には0から始めることができます.
原理は,左括弧と右括弧の整数を求めるために枝切りを迅速に行うことである.
右括弧の個数が左括弧より多い場合、または左括弧または右括弧の個数が半分を超える場合、そこから派生するDFS(右かっこで試行された最適化と同様)は必要ありません.
このようにDFSを回す場合、左かっこと右かっこの総数がnであれば、2つのカッコの総数が同じであれば、正解を加算します.
もちろん、すべての場合の数字は求められるので、Nが大きいほどCatalan数よりも時間がかかります.

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(int open, int close, int n, int depth)
{
    if(close > open)
        return;
    
    if(close > n / 2 || open > n / 2)
        return;
    
    if(open == close && open + close == n) 
        answer++;
    
    dfs(open + 1, close, n, depth + 1);
    dfs(open, close + 1, n, depth + 1);
}
int solution(int n) {
    dfs(0, 0, n << 1, 0);
    return answer;
}

DFSによる実装の結果