2014-03-20 03:27

题目：输出所有由N对括号组成的合法的括号序列。比如n=2，“()()”、“(())”等等。

解法：动态规划配合DFS，应该也叫记忆化搜索吧。一个整数N总可以拆成若干个正整数的和，执行搜索的时候也是按照这个规则，将N序列拆成多个子序列进行搜索，同时将中间的搜索结果记录下来，以便下次再搜到的时候直接调用，省掉重复计算的开销。

代码：

// 9.6 Print all valid parentheses sequences of n ()s.
#include
#include
#include
using namespace std;

void DFS(int idx, int n, string s, vector > &result)
{
if (idx == n) {
result[n].push_back(s);
return;
} else {
int i, j;
for (i = ; i <= n - idx; ++i) {
for (j = ; j < (int)result[i - ].size(); ++j) {
DFS(idx + i, n, s + '(' + result[i - ][j] + ')', result);
}
}
}
}

int main()
{
vector > result;
int n;
int i;

 result.resize();  
 result\[\].push\_back("");

 while (cin >> n && n > ) {  
     if (n >= (int)result.size()) {  
         for (i = (int)result.size(); i <= n; ++i) {  
             result.push\_back(vector<string>());  
             DFS(, i, "", result);  
         }  
     }  
     for (i = ; i < (int)result\[n\].size(); ++i) {  
         cout << result\[n\]\[i\] << endl;  
     }  
 }

 return ;  

}