通过动态编程平衡排列括号

Question

大家好，在非常著名的《破解代码》一书中，我遇到了一个问题：

实现一种算法，打印n对括号的所有有效（例如，正确打开和关闭）组合。

示例：

input: 3 (e.g., 3 pairs of parentheses)
output: ()()(), ()(()), (())(), ((()))
#include <iostream>
#include <string>
using namespace std;
void _paren(int l,int r,string s,int count);
void paren(int n)
{
    string s="";
    _paren(n,n,s,n);
}
void _paren(int l,int r,string s,int count){
    if(l<0 || r<0)
        return;
    if(l==0 && r==0)
        cout<<s<<endl;
    else{
        if(l>0)
        {
            _paren(l-1,r,s+"(",count+1);
        }
        if(r>l)
            _paren(l,r-1,s+")",count+1);                    
    }
}
int main(){
    int n;
    cin>>n;
    paren(n);
    return 0;
}

这是我尝试过的递归方法。我非常确信我们也可以通过动态编程来解决这个问题，因为我们已经一次又一次地使用了很多值，但我不知道如何通过动态编程实现这一点。我尝试了表格自下而上的方法，但没有成功。请帮我了解如何使用的基本想法

Answer 1

DP并不能真正帮助您。递归算法是时间和空间最优的！

事实上，不使用DP是有原因的：内存需求！这将是巨大的。

一个更好的算法是有一个传入的字符数组，让递归方法修改其中的一部分，并在需要时打印出来。我相信你提到的书中已经给出了解决方案。

Answer 2

DP可以通过每次调用选择最佳解决方案来减少遍历状态的数量。它还可以帮助您重用计算值。没有计算，必须访问每个有效状态，并且可以通过if（）避免无效状态。

我建议您实现另一个递归（至少在调用后不复制新的字符串对象，只需声明全局char数组并在需要时将其发送到输出）。

我对递归的想法是

char arr[maxN]; int n; // n is string length, must be even though
void func(int pos, int count) { // position in string, count of opened '('
   if( pos == n ) {
      for(int i = 0; i < n; i++)
         cout << char(arr[i]);
      cout << "n";
      return;
   }
   if( n-pos-1 > count ) {
      arr[pos] = '('; func(pos+1,count+1);
   }
   if( count > 0 ) {
      arr[pos] = ')'; func(pos+1,count-1);
   }
}

我没有检查，但我想这个想法很清楚。