C ++では、指定された位置に開き角かっこが含まれるようなバランスの取れた式ですか？

与えられた整数mと位置の配列'position[]'（1 <=length（position []）<=2m）の場合、長さ2mで構成できる適切なブラケット式の方法の数を見つけます。指定された位置には開き角かっこがあります。

注：position []配列は、（1ベースのインデックス）[0、1、1、0]の形式で提供されます。ここで1は、オープンブラケットを設定する位置を示しています。値が0の場合の位置では、開きブラケットまたは閉じブラケットのいずれかを設定できます。

例

Input: n = 2, position[] = [1, 0, 1, 0]
Output: 1
The only possibility is given below:
[ ] [ ]
In this case, recursive and recursion implementing memorization approach will be explained.

アルゴリズム

指定された配列adj1（say）のすべての位置を角かっこで開いて1としてマークする必要があります。

このようにして、再帰ループを実行します-

• 括弧の総数（閉じ括弧から下にある開き括弧）がゼロより小さい場合は、0を返します。

• インデックスがmまで到達し、括弧の合計が0に等しい場合、ソリューションが利用可能であり、1を返します。それ以外の場合は、0を返します。

• インデックス値に1が事前に割り当てられている場合は、index + 1を使用して関数を再帰的に返し、合計ブラケットをインクリメントする必要があります。

• それ以外の場合は、その位置またはインデックスに開いたブラケットを挿入し、合計ブラケットを1ずつインクリメントし、そのインデックスに閉じたブラケットを挿入し、合計ブラケットを1つ減らして、mまで次のインデックスに移動することにより、関数を再帰的に返す必要があります。

上記のアルゴリズムの場合の再帰的ソリューションは次のとおりです-

例

// C++ application of above method implementing Recursion
#include <bits/stdc++.h>
using namespace std;
// Function to locate or find Number of proper bracket expressions
int find(int index1, int openbrk1, int m, int adj1[]){
   // If open-closed brackets less than 0
   if (openbrk1 < 0)
   return 0;
   // If index reaches the end of expression
   if (index1 == m) {
      // If brackets are balanced
      if (openbrk1 == 0)
      return 1;
      else
      return 0;
   }
   // If the current index has assigned open bracket
   if (adj1[index1] == 1) {
      // We have to move forward increasing the
      // length of open brackets
      return find(index1 + 1, openbrk1 + 1, m, adj1);
   }
   else {
      // We have to move forward by inserting open as well
      // as closed brackets on that index
      return find(index1 + 1, openbrk1 + 1, m, adj1)
      + find(index1 + 1, openbrk1 - 1, m, adj1);
   }
}
// Driver Code
int main(){
   int m = 2;
   // Open brackets at position 1
   int adj1[4] = { 1, 0, 0, 0 };
   // Calling the find function to calculate the answer
   cout << find(0, 0, 2 * m, adj1) << endl;
   return 0;
}

出力

2

記憶されたアプローチ- 上記のアルゴリズムの時間計算量は、暗記を実装することで改善または最適化できます。

実行する必要があるのは、前の反復の結果を格納する配列を実装することだけです。これにより、値がすでに計算されている場合に同じ関数を複数回再帰的に呼び出す必要がなくなります。

以下は必須の実装です

// C++ application of above method implementing memorization
#include <bits/stdc++.h>
using namespace std;
#define M 1000
// Function to locate or find Number of proper bracket expressions
int find(int index1, int openbrk1, int m,
int dp1[M][M], int adj1[]){
   // If open-closed brackets is less than 0
   if (openbrk1 < 0)
   return 0;
   // If index attains or reaches the end of expression
   if (index1 == m) {
      // If brackets are balanced
      if (openbrk1 == 0)
      return 1;
      else
      return 0;
   }
   // If already stored in dp1
   if (dp1[index1][openbrk1] != -1)
   return dp1[index1][openbrk1];
   // If the current index has assigned open bracket
   if (adj1[index1] == 1) {
      // We have to move forward increasing the length of open brackets
      dp1[index1][openbrk1] = find(index1 + 1,
      openbrk1 + 1, m, dp1, adj1);
   }
   else {
      // We have to move forward by inserting open as
      // well as closed brackets on that index
      dp1[index1][openbrk1] = find(index1 + 1, openbrk1 + 1, m, dp1, adj1) + find(index1 + 1,             openbrk1 -    1, m, dp1, adj1);
   }
   // We have to return the answer
   return dp1[index1][openbrk1];
}
// Driver Code
int main(){
   // dp1 array to precalculate the answer
   int dp1[M][M];
   int m = 2;
   memset(dp1, -1, sizeof(dp1));
   // Open brackets at position 1
   int adj1[4] = { 1, 0, 0, 0 };
   // We have to call the find function to compute the answer
   cout<< find(0, 0, 2 * m, dp1, adj1) << endl;
   return 0;
}

出力

2

時間計算量：O（N2）