题目链接：?id=1141题目大意：给一些括号，求让它们合法最少要加上多少括号，并输出加上后的结果，合法的定义：1.空串是合法的2.若S是合法的，则［S］和（S）均是合法的3.若A和B是合法的，则AB是合法的题目分析：令dp[i][j]表示使子序列从i到j合法要加的最小括号数当子序列长度为1时，dp[i][i] = 1当子序列长度不为1时两个方案：1）dp[i] == ‘(‘ && dp[j] == ‘)’或者dp[i] == ‘[‘ && dp[j] == ‘]’说明最外侧已合法，则要加的括号数由里面的子序列决定即dp[i][j] = dp[i + 1][j – 1]2）枚举分割点，即i <= k < j，dp[i][j] = min(dp[i][k]，dp[k + 1][j])这样要添加的最少数量就能得到即dp[0][len – 1]，但是题目要输出序列，因此我们还要记录路径，若s[i] == s[j]则path[i][j] = -1，否则path[i][j] = k(分割点)，，输出的时候采用递归的方法见程序注释#include <cstdio>#include <cstring>int const INF = 0xfffffff;int const MAX = 105;int dp[MAX][MAX], path[MAX][MAX];char s[MAX];void Print(int i, int j){if(i > j) //无效位置return;if(i == j) //遇单个字符输出匹配后的结果{if(s[i] == '(' || s[i] == ')')printf("()");elseprintf("[]");}else if(path[i][j] == -1) //若i到j已经匹配，输出左边，递归中间再输出右边{printf("%c", s[i]);Print(i + 1, j – 1);printf("%c", s[j]);}else //否则，递归输出分割点两边{Print(i, path[i][j]);Print(path[i][j] + 1, j);}}int main(){while(gets(s)){int n = strlen(s);if(n == 0){printf("\n");continue;}memset(dp, 0, sizeof(dp));for(int i = 0; i < n; i++)dp[i][i] = 1;for(int l = 1; l < n; l++){for(int i = 0; i < n – l; i++){int j = i + l;dp[i][j] = INF;if((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']')){dp[i][j] = dp[i + 1][j – 1];path[i][j] = -1;}for(int k = i; k < j; k++){if(dp[i][j] > dp[i][k] + dp[k + 1][j]){dp[i][j] = dp[i][k] + dp[k + 1][j];path[i][j] = k;}}}}Print(0, n – 1);printf("\n");}}
世上没有绝望的处境，只有对处境绝望的人。
