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)