C++에서 주어진 위치에 여는 괄호가 있는 균형 잡힌 표현식?

주어진 정수 m과 위치 배열 'position[]'(1 <=length(position[]) <=2m)의 경우, 다음과 같이 길이 2m으로 구성할 수 있는 적절한 대괄호 표현식의 수를 구하십시오. 주어진 위치에는 여는 괄호가 있습니다.

참고:position[] 배열은 (1부터 인덱싱) [0, 1, 1, 0] 형식으로 제공됩니다. 여기서 1은 개방 브래킷을 설정해야 하는 위치를 나타냅니다. 값이 0인 경우 여는 괄호나 닫는 괄호를 설정할 수 있습니다.

예시

입력:n =2, position[] =[1, 0, 1, 0]출력:1다음은 유일한 가능성입니다.[ ] [ ]이 경우 재귀 및 재귀 구현 암기 접근 방식을 설명합니다. 
알고리즘
 

 주어진 배열 adj1(말)에서 여는 괄호가 있는 모든 위치를 1로 표시해야 합니다.
 

 이런 식으로 재귀 루프를 실행합니다 -
 
 
 

 여는 대괄호에서 닫는 대괄호를 뺀 총 대괄호의 개수가 0보다 작으면 0을 반환합니다.
 
 
 

 인덱스가 m까지 도달하고 전체 대괄호가 0이면 솔루션을 사용할 수 있으며 1을 반환하고 그렇지 않으면 0을 반환합니다.
 
 
 

 인덱스 값에 1이 미리 할당되어 있으면 index+1을 사용하여 재귀적으로 함수를 반환하고 전체 대괄호를 증가시켜야 합니다.
 
 
 

 그렇지 않으면 해당 위치 또는 인덱스에 열린 대괄호를 삽입하고 전체 대괄호를 1씩 증가시키고 해당 인덱스에 닫힌 대괄호를 삽입하고 전체 대괄호를 1씩 감소시켜 m까지 다음 인덱스로 이동하여 함수를 재귀적으로 반환해야 합니다.
 
 
 

 다음은 위 알고리즘의 경우 재귀 솔루션입니다 -
 
예시
 
// Recursion을 구현하는 위 메소드의 C++ 응용#include 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; 그렇지 않으면 0을 반환합니다. } // 현재 인덱스에 여는 대괄호가 할당된 경우 if (adj1[index1] ==1) { // 여는 대괄호의 길이를 // 증가시키면서 앞으로 나아가야 합니다. return find(index1 + 1, openbrk1 + 1, m, adj1); } else { // 해당 인덱스에 열린 괄호와 // 닫힌 괄호를 삽입하여 앞으로 나아가야 합니다. return find(index1 + 1, openbrk1 + 1, m, adj1) + find(index1 + 1, openbrk1 - 1, m , adj1); }}// 드라이버 코드int main(){ int m =2; // 위치 1에서 괄호 열기 int adj1[4] ={ 1, 0, 0, 0 }; // 답을 계산하기 위해 find 함수 호출 cout < 
출력
 
2
 

 암기된 접근 방식 - 위 알고리즘의 시간 복잡도는 Memorization을 구현하여 개선하거나 최적화할 수 있습니다.
 

 수행할 유일한 것은 값이 이미 계산된 경우 동일한 함수를 두 번 이상 재귀적으로 호출할 필요가 없도록 이전 반복의 결과를 저장하는 배열을 구현하는 것입니다.
 
다음은 필수 구현입니다.
 
// 암기를 구현하는 위 메소드의 C++ 적용#include 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; 그렇지 않으면 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 { // 해당 인덱스에 // 열린 괄호와 닫힌 괄호를 삽입하여 앞으로 나아가야 합니다. dp1[index1][openbrk1] =find(index1 + 1, openbrk1 + 1, m, dp1, adj1) + find( index1 + 1, openbrk1 - 1, m, dp1, adj1); } // 답을 반환해야 합니다. return dp1[index1][openbrk1];}// Driver Codeint main(){ // 답을 미리 계산하기 위한 dp1 배열 int dp1[M][M]; 정수 m =2; memset(dp1, -1, sizeof(dp1)); // 위치 1에서 괄호 열기 int adj1[4] ={ 1, 0, 0, 0 }; // 답을 계산하기 위해 find 함수를 호출해야 합니다. cout< 
출력
 
2
 

 시간 복잡도:O(N2)