记忆化搜索(DP+DFS) URAL 1183 Brackets Sequence

 1 /*
 2     记忆化搜索(DP+DFS)：dp[i][j] 表示第i到第j个字符，最少要加多少个括号
 3         dp[x][x] = 1 一定要加一个括号；dp[x][y] = 0, x > y;
 4         当s[x] 与 s[y] 匹配，则搜索 (x+1, y-1); 否则在x~y-1枚举找到相匹配的括号，更新最小值
 5 */
 6 #include <cstdio>
 7 #include <algorithm>
 8 #include <cmath>
 9 #include <iostream>
10 #include <cstring>
11 using namespace std;
12 
13 const int MAXN = 1e2 + 10;
14 const int INF = 0x3f3f3f3f;
15 int dp[MAXN][MAXN];
16 int pos[MAXN][MAXN];
17 char s[MAXN];
18 
19 void DFS(int x, int y)
20 {
21     if (dp[x][y] != -1)    return ;
22     if (x > y)        {dp[x][y] = 0;    return ;}
23     if (x == y)    {dp[x][y] = 1;    return ;}
24 
25     dp[x][y] = INF;
26     if ((s[x]=='(' && s[y]==')') || (s[x]=='[' && s[y]==']'))
27     {
28         pos[x][y] = -1;
29         DFS (x+1, y-1);
30         dp[x][y] = dp[x+1][y-1];
31     }
32     for (int i=x; i<y; ++i)
33     {
34         DFS (x, i);    DFS (i+1, y);
35         int cur = dp[x][i] + dp[i+1][y];
36         if (cur < dp[x][y])
37         {
38             dp[x][y] = cur;        pos[x][y] = i;
39         }
40     }
41 }
42 
43 void print(int x, int y)
44 {
45     if (x > y)    return ;
46     if (x == y)
47     {
48         if (s[x] == '(' || s[y] == ')')    printf ("()");
49         else    printf ("[]");
50         return ;
51     }
52     if (pos[x][y] == -1)
53     {
54         printf ("%c", s[x]);
55         print (x+1, y-1);
56         printf ("%c", s[y]);
57     }
58     else
59     {
60         print (x, pos[x][y]);    print (pos[x][y]+1, y);
61     }
62 }
63 
64 int main(void)        //URAL 1183 Brackets Sequence
65 {
66     //freopen ("O.in", "r", stdin);
67 
68     while (scanf ("%s", s+1) == 1)
69     {
70         int len = strlen (s+1);
71         memset (dp, -1, sizeof (dp));
72         memset (pos, 0, sizeof (pos));
73 
74         DFS (1, len);
75         print (1, len);    puts ("");
76     }
77 
78     return 0;
79 }
编译人生，运行世界！