递归创建——nested()

Question

我正在尝试解决“经典”动态规划问题之一。问题是 - 给定一个数字作为输入，生成可能的嵌套条件。

编辑：正如下面的 temp 所指出的，我将首先尝试使用递归来解决这个问题，然后尝试使用动态编程。

IE。 if 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;
}

调试：

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

我明白为什么列表中有重复的值。即，一旦使用递归调用函数并最终执行下一个分支。第二次打印是由于它本身落在第二个分支上的函数。有什么办法可以处理这个问题吗？我实在不想走全球统一的路线。

另外，在我的脑海中，这段代码应该打印 (())() - 但它没有:(

有人可以指出错误吗？

谢谢！

我知道情况需要一些调整，但我一直在无休止地盯着这个。哈普！

Answer 1

目前，您的解决方案没有利用动态编程。如果你想在这里使用DP，你需要递归地思考问题。幸运的是，这个问题有一个很好的递归公式：

1. 只有一种方法可以从没有括号的情况得到平衡的括号，那就是根本没有括号。
2. 如果需要平衡 n + 1 对括号，则可以按如下方式生成所有平衡括号：对于从 0 到 n 的所有 i，构造 (X)Y 形式的每个字符串，其中 < code>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";
}