题意：给出一个括号串，求最短的满足要求的括号串；
思路：枚举长度，枚举起点和终点，找到匹配括号是可递推到子序列，枚举中间指针求最优解；打印时通过记忆表path存储最优解，递归求出最短序列；
#include<cstdio> #include<cstring> #include<algorithm> #define INF 0x7fffffff using namespace std; char str[505]; int dp[505][505]; int path[505][505]; void oprint(int i,int j) {if(i>j) return;if(i==j){if(str[i]=='['||str[i]==']')printf("[]");else printf("()");}else if(path[i][j]==-1){printf("%c",str[i]);oprint(i+1,j-1);printf("%c",str[j]);}else{oprint(i,path[i][j]);oprint(path[i][j]+1,j);} } int main() {gets(str);int n=strlen(str);if(n==0){printf("\n");return 0;}memset(path,0,sizeof(path));memset(dp,0,sizeof(dp));for(int i=0;i<n;i++)dp[i][i]=1;for(int r=1;r<=n;r++)//递推子序列长度 {for(int i=0;i<n-r;i++)//枚举起点 {int j=i+r;//计算子序列的结束位置dp[i][j]=0x7fffffff;if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']')){dp[i][j]=dp[i+1][j-1];}path[i][j]=-1;//放在外面，否则WAfor(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;}}}}oprint(0,n-1);printf("\n");return 0; }