平衡的表达式，例如给定位置在C ++中有开括号？

Z时代
2024-01-10
分类：综合

在给定整数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;
//查找或查找适当括号表达式的功能
int find(int index1, int openbrk1, int m, int adj1[]){
   //如果开括号小于0-
   if (openbrk1 < 0)
   return 0;
   //如果索引到达表达式的末尾
   if (index1 == m) {
      //如果括号是平衡的
      if (openbrk1 == 0)
      return 1;
      else
      return 0;
   }
   //如果当前索引已分配了方括号
   if (adj1[index1] == 1) {
      //我们必须继续提高
      //开括号的长度
      return find(index1 + 1, openbrk1 + 1, m, adj1);
   }
   else {
      //我们还必须插入open-
      //作为该索引的方括号
      return find(index1 + 1, openbrk1 + 1, m, adj1)
      + find(index1 + 1, openbrk1 - 1, m, adj1);
   }
}
//驱动程式码
int main(){
   int m = 2;
   //打开括号
   int adj1[4] = { 1, 0, 0, 0 };
   //调用find函数计算答案
   cout << find(0, 0, 2 * m, adj1) << endl;
   return 0;
}

输出结果

记忆方式-通过实施记忆可以改善或优化上述算法的时间复杂度。

唯一要执行的是实现一个数组，以存储先前迭代的结果，因此，如果已经计算出该值，则不需要多次递归调用同一函数。

以下是必需的实现

// C++ application of above method implementing memorization
#include <bits/stdc++.h>
using namespace std;
#define M 1000
//查找或查找适当括号表达式的功能
int find(int index1, int openbrk1, int m,
int dp1[M][M], int adj1[]){
   //如果开括号小于0-
   if (openbrk1 < 0)
   return 0;
   //如果索引达到或到达表达式的末尾
   if (index1 == m) {
      //如果括号是平衡的
      if (openbrk1 == 0)
      return 1;
      else
      return 0;
   }
   //如果已经存储在dp1中
   if (dp1[index1][openbrk1] != -1)
   return dp1[index1][openbrk1];
   //如果当前索引已分配了方括号
   if (adj1[index1] == 1) {
      //我们必须继续提高开括号的长度
      dp1[index1][openbrk1] = find(index1 + 1,
      openbrk1 + 1, m, dp1, adj1);
   }
   else {
      //我们必须向前插入open as-
      // well作为该索引的方括号
      dp1[index1][openbrk1] = find(index1 + 1, openbrk1 + 1, m, dp1, adj1) + find(index1 + 1,             openbrk1 -    1, m, dp1, adj1);
   }
   //我们必须返回答案
   return dp1[index1][openbrk1];
}
//驱动程式码
int main(){
   //dp1数组以预先计算答案
   int dp1[M][M];
   int m = 2;
   memset(dp1, -1, sizeof(dp1));
   //打开括号
   int adj1[4] = { 1, 0, 0, 0 };
   //我们必须调用find函数来计算答案
   cout<< find(0, 0, 2 * m, dp1, adj1) << endl;
   return 0;
}