DP问题实现的要点就是， 先求子问题。
设dp[i,j]为从位置i到位置j需要加入字符的最小次数，有dp[i,j]=min(dp[i,k]+dp[k+1,j])，其中i<=k<j。特别的当s[i]='[' s[j]=']'或者s[i]='(' s[j]=')'时，dp[i,j]=dp[i+1,j-1]。初始条件为dp[i,i]=1，其中0<=i<len。
如上述这题的dp方程
发现dp[i][j]依赖于两个dp[i][k], dp[k+1][j]
因此要先求所依赖的这两项才行。
想办法怎么能先求这两项，只能是枚举串长度，从2到n
类似矩阵链乘法。
其余的DP题也都是，看看怎么先求子问题，如果直接循环就搞定，比如一般的题都只依赖于前一个，那么循环就完事了。就ok。不然比如这题依赖两个，那么要考虑怎么先求解子问题了。
这道题有个易错点，就是
str[i] == '(' && str[j] == ')'时候，或者
str[i] == '[' && str[j] == ']'时候，就是两端恰好配对的时候
并不能任务dp[i][j] = dp[i+1][j-1]。 反例就是()()这种情况
而是无论什么时候都要用k做分割，然后两端相等的时候dp[i][j] = min(dp[i][j], dp[i+1][j-1])，并且把path[i][j] = -1（如果dp[i][j]选了dp[i+1][j-1]）。
之前写成if-else了就WA了
dp[i][j] = min(dp[i][k], dp[k+1][j]) i<=k<j
dp[i][j] = min(dp[i][j], dp[i+1][j-1])
#include <iostream>
#include <memory>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <climits>
using namespace std;
const int MAXN = 110;
char str[MAXN];
int dp[MAXN][MAXN],path[MAXN][MAXN];
void print(int i, int j)
{
if (i > j) return;
if (i == j) {
if (str[i] == '('|| str[i]==')') {
printf("()");
return;
} else if (str[i] == '['||str[i]==']') {
printf("[]");
return;
}
}
if (path[i][j] == -1) {
printf("%c", str[i]);
print(i+1, j-1);
printf("%c", str[j]);
} else {
print(i, path[i][j]);
print(path[i][j]+1, j);
}
}
int main()
{
int i,j,k,r,n;
while (gets(str)) {
n = strlen(str);
if (n==0) {
printf("\n");
continue;
}
memset(dp, 0, sizeof(dp));
memset(path, -1, sizeof(path));
j = 0;
for (i = 0; i < n; i++)
dp[i][i] = 1;
for (r = 2; r <= n; r++)
for (i = 0, j=i+r-1; i < n && j < n; i++, j=i+r-1) {
dp[i][j] = 9999999;
path[i][j] = -1;
int m;
for (k = i; k <j; k++) {
m = dp[i][k] + dp[k+1][j];
if (m < dp[i][j]) {
dp[i][j] = m;
path[i][j] = k;
}
}
if ((str[i] == '[' && str[j] == ']') ||
(str[i] == '(' && str[j] == ')')) {
if (dp[i+1][j-1] < dp[i][j]) {
dp[i][j] = dp[i+1][j-1];
path[i][j] = -1;
}
}
}
//cout<<dp[0][n-1]<<endl;
print(0, n-1);
printf("\n");
}
}