題目描述：
定義合法的括號序列如下：
1 空序列是一個合法的序列
2 如果S是合法的序列，則(S)和[S]也是合法的序列
3 如果A和B是合法的序列，則AB也是合法的序列
例如：下面的都是合法的括號序列
(), [], (()), ([]), ()[], ()[()]
下面的都是非法的括號序列
(, [, ), )(, ([)], ([(]
給定一個由'(', ')', '[', 和 ']' 組成的序列，找出以該序列為子序列的最短合法序列。
思路：真是經典的題目，區間DP，題目居然有陷阱，輸入可能是空串,所以用scanf的時候，會不讀入，就少了一次讀入，wa
所以用gets
// Accepted C++ 1.002 2015-03-12 13:34:47
#include
#include
#include
#include
using namespace std;
const int inf= 0x3f3f3f3f;
int dp[105][105];
char str[105];
int n;
bool match(char a,char b)
{
if(a=='('&&b==')') return true;
else if(a=='[' && b==']') return true;
return false;
}
void print(int l,int r) //遞歸打印解
{
if(l>r) return ;
if(l==r)
{
if(str[l]=='('||str[l]==')') printf("()");
else if(str[l]=='['||str[l]==']') printf("[]");
return ;
}
if(match(str[l],str[r])&&dp[l][r]==dp[l+1][r-1])
//別忘了match(str[l],str[r])，因為dp[l][r]==dp[l+1][r-1]時候，不一定外側括號匹配，很容易錯
{
putchar(str[l]);
print(l+1,r-1);
putchar(str[r]);
return ;
}
for(int k=l;k
