นิพจน์ที่สมดุลซึ่งตำแหน่งที่กำหนดมีวงเล็บเปิดใน C ++ หรือไม่

ในกรณีของจำนวนเต็ม m ที่กำหนดและอาร์เรย์ของตำแหน่ง 'position[]' (1 <=length(position[]) <=2m) ให้ค้นหาจำนวนวิธีของนิพจน์วงเล็บที่เหมาะสมซึ่งสามารถสร้างความยาวได้ 2 ม. ตำแหน่งที่กำหนดมีวงเล็บเปิด

หมายเหตุ:ตำแหน่ง [] อาร์เรย์มีให้ในรูปแบบของ (การทำดัชนีแบบ 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 (พูด) เป็น 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)