Рубрики

Сбалансированные выражения, так что заданные позиции имеют открывающие скобки

Для заданного целого числа n и массива позиций 'position []' (1 <= position [i] <= 2n) найдите количество способов правильных выражений скобок, которые можно сформировать длиной 2n, чтобы у данных позиций была открывающая скобка ,

Примеры :

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:
[ ] [ ]

Подход: эта проблема может быть решена с помощью динамического программирования . ,

Пусть DP i, j будет количеством допустимых способов заполнения первых i позиций так, чтобы на j было больше скобок типа '[', чем типа ']'. Допустимые пути означают, что это префикс выражения с совпадающими скобками и что места, в которых применяются принудительные скобки '[', были выполнены. Легко видеть, что DP 2N, 0 является окончательным ответом.

Базовый случай DP — DP 0, 0 = 1. Нам нужно заполнить первую позицию скобкой '[', и для этого есть только один способ.

Если позиция имеет последовательность открывающих скобок, которая может быть помечена хеш-массивом, то повторение происходит так:

if(j != 0) dpi, j = dpi-1, j-1
else  dpi, j =  0; 

Если позиция не имеет последовательности открывающей скобки , то повторение происходит как:

if(j != 0) dpi, j = dpi - 1, j - 1 + dpi - 1, j + 1
 else  dpi, j = dpi - 1, j + 1

Ответом будет DP 2n, 0

Ниже приводится реализация вышеуказанного подхода:

C ++

// код CPP, чтобы найти количество способов
// расставляем скобки с правильными выражениями
#include <bits/stdc++.h>

using namespace std;

  
#define N 1000

  
// функция для вычисления числа
// правильной последовательности скобок

long long arrangeBraces(int n, int pos[], int k)

{

  

    // хеш-массив для пометки

    // позиции открывающих скобок

    bool h[N];

  

    // массив dp 2d

    int dp[N][N];

  

    memset(h, 0, sizeof h);

    memset(dp, 0, sizeof dp);

  

    // помечаем позиции в массиве хэшей

    for (int i = 0; i < k; i++)

        h[pos[i]] = 1;

  

    // первая позиция помечена как 1

    dp[0][0] = 1;

  

    // повторяем и формулируем повторения

    for (int i = 1; i <= 2 * n; i++) {

        for (int j = 0; j <= 2 * n; j++) {

  

            // если позиция имеет открывающую скобку

            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 dp[2 * n][0];

}

  
// код драйвера

int main()

{

    int n = 3;

  

    // позиции, где открывающие скобки

    // будет размещен

    int pos[] = { 2 };

    int k = sizeof(pos)/sizeof(pos[0]);

  

    cout << arrangeBraces(n, pos, k);

    return 0;

}

Джава

// Java-код для поиска количества способов
// расставляем скобки с правильными выражениями

  

public class GFG {

  

    static final int N = 1000;

  
// функция для вычисления числа
// правильной последовательности скобок

    static long arrangeBraces(int n, int pos[], int k) {

  

        // хеш-массив для пометки

        // позиции открывающих скобок

        boolean h[] = new boolean[N];

  

        // массив dp 2d

        int dp[][] = new int[N][N];

  

        // помечаем позиции в массиве хэшей

        for (int i = 0; i < k; i++) {

            h[pos[i]] = true;

        }

  

        // первая позиция помечена как 1

        dp[0][0] = 1;

  

        // повторяем и формулируем повторения

        for (int i = 1; i <= 2 * n; i++) {

            for (int j = 0; j <= 2 * n; j++) {

  

                // если позиция имеет открывающую скобку

                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 dp[2 * n][0];

    }

// Код драйвера

  

    public static void main(String[] args) {

        int n = 3;

  

        // позиции, где открывающие скобки

        // будет размещен

        int pos[] = {2};

        int k = pos.length;

        System.out.print(arrangeBraces(n, pos, k));

    }

}
// Этот код предоставлен 29AjayKumar

python3

# Python 3 код, чтобы найти количество способов
# расстановка скобок с правильными выражениями

N = 1000

  
# функция для вычисления числа
# правильной последовательности скобок

def arrangeBraces(n, pos, k):

      

    # хэш-массив для пометки

    # позиции открывающих скобок

    h = [False for i in range(N)] 

  

    # dp 2d array

    dp = [[0 for i in range(N)]

             for i in range(N)] 

  

    # помечать позиции в массиве хэшей

    for i in range(k): 

        h[pos[i]] = 1

  

    # первая позиция отмечена как 1

    dp[0][0] = 1

  

    # повторять и формулировать повторения

    for i in range(1, 2 * n + 1):

        for j in range(2 * n + 1):

              

            # если позиция имеет открывающую скобку

            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 dp[2 * n][0]

  
Код водителя

n = 3

  
# позиции, где открываются фигурные скобки
# будет размещен

pos = [ 2 ,]; 

k = len(pos) 

print(arrangeBraces(n, pos, k))

  
# Этот код добавлен
# от sahishelangia

C #

// C # код для поиска количества способов
// расставляем скобки с правильными выражениями

using System; 

    

class GFG 

    static int N = 1000; 

    

    // функция для вычисления числа

    // правильной последовательности скобок

    public static long arrangeBraces(int n, int[] pos, int k) 

    

        

        // хеш-массив для пометки

        // позиции открывающих скобок

        bool[] h = new bool[N]; 

        

        // массив dp 2d

        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;

        

        // помечаем позиции в массиве хэшей

        for (int i = 0; i < k; i++) 

            h[pos[i]] = true

        

        // первая позиция помечена как 1

        dp[0,0] = 1; 

        

        // повторяем и формулируем повторения

        for (int i = 1; i <= 2 * n; i++) { 

            for (int j = 0; j <= 2 * n; j++) { 

        

                // если позиция имеет открывающую скобку

                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 dp[2 * n,0]; 

    

        

    // код драйвера

    static void Main() 

    

        int n = 3; 

          

        // позиции, где открывающие скобки

        // будет размещен

        int[] pos = new int[]{ 2 }; 

        int k = pos.Length; 

        

        Console.Write(arrangeBraces(n, pos, k)); 

    }

    // Этот код предоставлен DrRoot_

}

Выход :

3

Сложность времени: O (n ^ 2)
Вспомогательное пространство: O (n ^ 2)

Рекомендуемые посты:

Сбалансированные выражения, так что заданные позиции имеют открывающие скобки

0.00 (0%) 0 votes