创建的递归 - 嵌套()

Question

我试图解决一个"经典"动态编程问题.问题是 - 给定一个数字作为输入,生成可能的嵌套条件.

编辑:正如下面的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;
}

调试:

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

我理解为什么列表中有重复的值.即一旦使用递归调用函数,并在执行时跟随下一个分支结束.第二次打印是由于它自身落在第二个分支上的功能.有办法处理这个吗？我真的不想走全球化的路线.

另外,在我脑海中这段代码应该打印(())() - 但它不会:(

有人可以指出错误吗？

谢谢!

我知道这种情况需要一些调整,但我一直在无休止地盯着这个.HALP!

Answer 1

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

1. 只有一种方法可以从括号中取出平衡括号,即根本没有括号.
2. 如果你有n + 1对括号来平衡,那么你可以生成所有平衡括号,如下所示:对于从0到n的所有i,构造表格的每个字符串(X)Y,其中X是一个i平衡括号Y的字符串,是一个字符串n - 我平衡括号.

这个设置的美妙之处在于,要计算n + 1个平衡括号的所有字符串,你只需要知道如何为0,1,2,...,n + 1制作平衡括号.因此,你可以解决这个问题通过迭代构造n = 0,1,2,...等的解决方案,并重用您在前面步骤中生成的结果.

希望这可以帮助!