Trong trường hợp một số nguyên m cho trước và một mảng các vị trí 'position []' (1 <=length (position []) <=2m), hãy tìm số cách biểu thức dấu ngoặc thích hợp có thể tạo được chiều dài 2m sao cho các vị trí đã cho có dấu ngoặc mở.
Lưu ý:mảng position [] được cung cấp dưới dạng (lập chỉ mục dựa trên 1) [0, 1, 1, 0]. Ở đây 1 chỉ ra các vị trí mà tại đó dấu ngoặc nhọn sẽ được đặt. Tại các vị trí trong trường hợp giá trị 0, có thể đặt dấu ngoặc mở hoặc đóng ngoặc.
Ví dụ
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.
Thuật toán
Chúng ta phải đánh dấu tất cả các vị trí có dấu ngoặc mở trong mảng adj1 đã cho (giả sử) là 1.
Chúng tôi chạy một vòng lặp đệ quy, theo cách này -
-
Nếu số tổng số dấu ngoặc (dấu ngoặc mở trừ từ dấu ngoặc đóng) nhỏ hơn 0, trả về 0.
-
Nếu chỉ số đạt được cho đến m và nếu tổng số dấu ngoặc bằng 0, thì một giải pháp có sẵn và trả về 1, ngược lại trả về 0.
-
Nếu giá trị chỉ mục có 1 được gán trước cho nó, chúng ta phải trả về hàm một cách đệ quy với chỉ mục + 1 và tăng tổng số dấu ngoặc.
-
Nếu không, chúng ta phải trả lại hàm một cách đệ quy bằng cách chèn các dấu ngoặc mở tại vị trí hoặc chỉ mục đó và tăng tổng số dấu ngoặc lên 1 + chèn dấu ngoặc đóng tại chỉ mục đó và giảm tổng số dấu ngoặc đi 1 và chuyển sang chỉ mục tiếp theo cho đến m.
Sau đây là giải pháp đệ quy trong trường hợp thuật toán trên -
Ví dụ
// 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;
} Đầu ra
2
Phương pháp tiếp cận được ghi nhớ - Độ phức tạp về thời gian của thuật toán trên có thể được cải thiện hoặc tối ưu hóa bằng cách triển khai tính năng Ghi nhớ.
Điều duy nhất cần thực hiện là triển khai một mảng để lưu trữ kết quả của các lần lặp trước đó để không yêu cầu gọi đệ quy cùng một hàm nhiều lần nếu giá trị đã được tính toán.
Sau đây là triển khai bắt buộc
// 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;
}
Đầu ra
2
Độ phức tạp về thời gian:O (N2)