Dado un entero n y una array de posiciones ‘posición []’ (1 <= posición [i] <= 2n), encuentre el número de formas de expresiones de paréntesis adecuadas que se pueden formar de longitud 2n de modo que las posiciones dadas tengan paréntesis de apertura .
Ejemplos:
Input : n = 3, position[] = [2} Output : 3 Explanation : The proper bracket sequences of length 6 and opening bracket at position 2 are: [ [ ] ] [ ] [ [ [ ] ] ] [ [ ] [ ] ] Input : n = 2, position[] = {1, 3} Output : 1 Explanation: The only possibility is: [ ] [ ]
Enfoque: Este problema se puede resolver mediante programación dinámica . .
Sea DP i, j el número de formas válidas de llenar las primeras i posiciones de modo que haya j más corchetes de tipo ‘[‘ que de tipo ‘]’. Las formas válidas significarían que es el prefijo de una expresión de paréntesis coincidente y que se han cumplido las ubicaciones en las que se aplican los corchetes ‘[‘. Es fácil ver que DP 2N, 0 es la respuesta final.
El caso base del DP es, DP 0, 0 =1. Necesitamos llenar la primera posición con un corchete ‘[‘, y solo hay una forma de hacerlo.
Si la posición tiene una secuencia de paréntesis de aperturaque se puede marcar con una array hash, entonces la recurrencia ocurre como:
if(j != 0) dpi, j = dpi-1, j-1 else dpi, j = 0;
Si la posición no tiene una secuencia de paréntesis de apertura , la recurrencia ocurre como:
if(j != 0) dpi, j = dpi - 1, j - 1 + dpi - 1, j + 1 else dpi, j = dpi - 1, j + 1
La respuesta será DP 2n, 0
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP code to find number of ways of // arranging bracket with proper expressions #include <bits/stdc++.h> using namespace std; #define N 1000 // function to calculate the number // of proper bracket sequence long long arrangeBraces(int n, int pos[], int k) { // hash array to mark the // positions of opening brackets bool h[N]; // dp 2d array int dp[N][N]; memset(h, 0, sizeof h); memset(dp, 0, sizeof dp); // mark positions in hash array for (int i = 0; i < k; i++) h[pos[i]] = 1; // first position marked as 1 dp[0][0] = 1; // iterate and formulate the recurrences for (int i = 1; i <= 2 * n; i++) { for (int j = 0; j <= 2 * n; j++) { // if position has a opening bracket if (h[i]) { if (j != 0) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = 0; } else { if (j != 0) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; else dp[i][j] = dp[i - 1][j + 1]; } } } // return answer return dp[2 * n][0]; } // driver code int main() { int n = 3; // positions where opening braces // will be placed int pos[] = { 2 }; int k = sizeof(pos)/sizeof(pos[0]); cout << arrangeBraces(n, pos, k); return 0; }
Java
// Java code to find number of ways of // arranging bracket with proper expressions public class GFG { static final int N = 1000; // function to calculate the number // of proper bracket sequence static long arrangeBraces(int n, int pos[], int k) { // hash array to mark the // positions of opening brackets boolean h[] = new boolean[N]; // dp 2d array int dp[][] = new int[N][N]; // mark positions in hash array for (int i = 0; i < k; i++) { h[pos[i]] = true; } // first position marked as 1 dp[0][0] = 1; // iterate and formulate the recurrences for (int i = 1; i <= 2 * n; i++) { for (int j = 0; j <= 2 * n; j++) { // if position has a opening bracket if (h[i]) { if (j != 0) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = 0; } } else if (j != 0) { dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; } else { dp[i][j] = dp[i - 1][j + 1]; } } } // return answer return dp[2 * n][0]; } // Driver code public static void main(String[] args) { int n = 3; // positions where opening braces // will be placed int pos[] = {2}; int k = pos.length; System.out.print(arrangeBraces(n, pos, k)); } } // This code is contributed by 29AjayKumar
Python3
# Python 3 code to find number of ways of # arranging bracket with proper expressions N = 1000 # function to calculate the number # of proper bracket sequence def arrangeBraces(n, pos, k): # hash array to mark the # positions of opening brackets h = [False for i in range(N)] # dp 2d array dp = [[0 for i in range(N)] for i in range(N)] # mark positions in hash array for i in range(k): h[pos[i]] = 1 # first position marked as 1 dp[0][0] = 1 # iterate and formulate the recurrences for i in range(1, 2 * n + 1): for j in range(2 * n + 1): # if position has a opening bracket if (h[i]): if (j != 0): dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 0 else: if (j != 0): dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) else: dp[i][j] = dp[i - 1][j + 1] # return answer return dp[2 * n][0] # Driver Code n = 3 # positions where opening braces # will be placed pos = [ 2 ,]; k = len(pos) print(arrangeBraces(n, pos, k)) # This code is contributed # by sahishelangia
C#
// C# code to find number of ways of // arranging bracket with proper expressions using System; class GFG { static int N = 1000; // function to calculate the number // of proper bracket sequence public static long arrangeBraces(int n, int[] pos, int k) { // hash array to mark the // positions of opening brackets bool[] h = new bool[N]; // dp 2d array int[,] dp = new int[N,N]; for(int i = 0; i < N; i++) h[i] = false; for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) dp[i,j] = 0; // mark positions in hash array for (int i = 0; i < k; i++) h[pos[i]] = true; // first position marked as 1 dp[0,0] = 1; // iterate and formulate the recurrences for (int i = 1; i <= 2 * n; i++) { for (int j = 0; j <= 2 * n; j++) { // if position has a opening bracket if (h[i]) { if (j != 0) dp[i,j] = dp[i - 1,j - 1]; else dp[i,j] = 0; } else { if (j != 0) dp[i,j] = dp[i - 1,j - 1] + dp[i - 1,j + 1]; else dp[i,j] = dp[i - 1,j + 1]; } } } // return answer return dp[2 * n,0]; } // driver code static void Main() { int n = 3; // positions where opening braces // will be placed int[] pos = new int[]{ 2 }; int k = pos.Length; Console.Write(arrangeBraces(n, pos, k)); } //This code is contributed by DrRoot_ }
Javascript
<script> // Javascript code to find number of ways of // arranging bracket with proper expressions let N = 1000; // function to calculate the number // of proper bracket sequence function arrangeBraces(n, pos, k) { // hash array to mark the // positions of opening brackets let h = new Array(N); h.fill(false); // dp 2d array let dp = new Array(N); for (let i = 0; i < N; i++) { dp[i] = new Array(N); for (let j = 0; j < N; j++) { dp[i][j] = 0; } } // mark positions in hash array for (let i = 0; i < k; i++) { h[pos[i]] = true; } // first position marked as 1 dp[0][0] = 1; // iterate and formulate the recurrences for (let i = 1; i <= 2 * n; i++) { for (let j = 0; j <= 2 * n; j++) { // if position has a opening bracket if (h[i]) { if (j != 0) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = 0; } } else if (j != 0) { dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; } else { dp[i][j] = dp[i - 1][j + 1]; } } } // return answer return dp[2 * n][0]; } let n = 3; // positions where opening braces // will be placed let pos = [2]; let k = pos.length; document.write(arrangeBraces(n, pos, k)); </script>
Producción :
3
Complejidad de tiempo: O(n^2)
Espacio auxiliar: O(n^2)