c++ - 递归创建——nested()

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;
}

调试:

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

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

另外，在我看来，这段代码应该打印 (())() - 但它没有:(

有人可以指出错误吗？

谢谢!

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

Answer 1

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

1. 只有一种方法可以从无括号生成平衡括号，即根本没有括号。
2. 如果要平衡 n + 1 对括号，则可以按如下方式生成所有平衡括号:对于从 0 到 n 的所有 i，构造 (X)Y 形式的每个字符串，其中 X 是由 i 个平衡括号组成的字符串，Y 是由 n - i 个平衡括号组成的字符串。

此设置的优点在于，要计算 n + 1 个平衡括号的所有字符串，您只需要知道如何为 0, 1, 2, ..., n + 1 创建平衡括号。因此，您可以通过迭代构建 n = 0、1、2、...等的解决方案并重用您在前面步骤中生成的结果来解决此问题。

希望这有帮助!