Рекурсия для создания - вложенная ()

Question

Я пытаюсь решить одну из «классических» задач динамического программирования. Проблема в том, что - учитывая число в качестве входных данных, генерировать возможные вложенные условия.

Edit: как указано в temp ниже, я собираюсь сначала попытаться разобраться с помощью рекурсии, а затем попробовать с динамическим программированием.

есть. если n = 3

O/p
((()))
()()()
(())()
()(())
(()())

Мой подход к проблеме основан на двух правилах.

1. Добавьте скобку "(", если максимальное число ( тут 3) не дошел и номер левых скобок меньше или равно на количество правильных скобок.
2. Добавлять правильную скобку, только если максимальное число является не достигнуто и номер прав брекеты меньше количества левых фигурные скобки.

Теоретически, они звучат правильно, но на приведенном ниже источнике он падает лицом вниз. Пожалуйста, извините за жесткое кодирование.

Редактировать: я сделал некоторые изменения и подвинулся на дюйм ближе к решению:)

 #include <iostream>
#include <vector>
#include <string>

using namespace std;

void printPar(int l,int r,string s)
{
    if(l > 3 || r > 3 || r >l)
        return;



    if(l==3 && r==3)
    {
        cout<<s<<endl;
        return;
    }
    else
    {

         if((l<3))
         {
            s+="<";
            l = l+1;
            printPar(l,r,s);
         }
          if(r<3 && r < l)
         {
             s+=">";
             r = r+1;
            printPar(l,r,s);
         }
       //  cout<<"Exiting "<<l<<" & "<<r<<" "<<s<<endl;
    }
}




int main()
{
    string s;
    printPar(0,0,s);
    return 0;
}

Debug:

<<<>>>
<<<>>>
<<><>>
<<><>>
<><<>>
<><<>>
<><><>
<><><>

Я понимаю, почему в списке есть повторяющиеся значения. т.е. когда функция вызывается с использованием рекурсии и заканчивается выполнением следующей ветви. Второй отпечаток происходит из-за того, что функция самостоятельно падает на вторую ветвь. Есть ли способ справиться с этим? Я действительно не хочу идти по глобальному маршруту.

Кроме того, в моей голове этот код должен напечатать (()) () - но это не так: (

Может кто-нибудь указать на ошибку?

Спасибо!

Я знаю, что состояние нуждается в доработке, но я смотрел на это бесконечно. Halp!

Answer 1

В данный момент ваше решение не использует преимущества динамического программирования.Если вы хотите использовать DP здесь, вам нужно рекурсивно подумать о проблеме.К счастью, есть замечательная рекурсивная формулировка этой проблемы:

1. Существует только один способ сделать сбалансированные скобки без скобок, а именно - вообще не иметь скобок.
2. Если вычтобы сбалансировать n + 1 пар скобок, вы можете сгенерировать все сбалансированные скобки следующим образом: для всех i от 0 до n создайте каждую строку в форме (X)Y, где X - строка из сбалансированных скобок i иY - это строка из n - i сбалансированных скобок.

Прелесть этой настройки в том, что для вычисления всех строк n + 1 сбалансированных скобок вам нужно знать только то, как сделать сбалансированные скобкидля 0, 1, 2, ..., n + 1. Следовательно, вы можете решить эту проблему путем итеративного построения решений для n = 0, 1, 2, ... и т. д. и повторного использования результатов, полученных на предыдущих этапах.

Надеюсь, это поможет!

Answer 2

Я думаю, что это должно решить вашу проблему.

// this map will contain all valid balanced paranthesis expressions
// string will hold expressions
// int for holding 'n' ie number of '('
map<string,int> mvc;

//fn to create all possible balanced set of paranthesis, for given n
void printAllBP(int);
//print fn
void printAll(int);

int main()
{
    int n;
    cout << "Enter n: ";
    cin >> n;

    printAllBP(n);
    printAll(n);

    system("pause");
    return 0;
}

void printAllBP(int n)
{
    if (0==n)
    {
        mvc.insert(pair<string,int>("",0));
        return;
    }    

    printAllBP(n-1);

    map<string,int>::iterator it;
    for (it=mvc.begin();it!=mvc.end();++it)
    {
        if((n-1)==(*it).second)
        {
            string t=(*it).first;
            mvc.insert(pair<string,int>("()"+t,n));
            mvc.insert(pair<string,int>("("+t+")",n));
            mvc.insert(pair<string,int>(t+"()",n));
        }
    }
}

void printAll(int n)
{
    cout << "Printing all possiblities for '" << n << "':\n";
    map<string,int>::iterator it;
    for ( it=mvc.begin();it != mvc.end();++it)
    {
        if(n==(*it).second)
            cout << "\n" << (*it).first;
    }
    cout << "\n";
}