dp[x][y]表示 [x,y] 里的最大匹配, 如果 s[x]和 s[y]匹配, 那么 dp[x][y] = dp[x + 1][y - 1] + 2. 然后对于每个区间都试图将其拆成两半.
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- char s[200];
- int dp[200][200];
- int dfs(int x,int y)
- {
- if (x>= y)
- return 0;
- if (dp[x][y] != -1)
- return dp[x][y];
- if ((s[x] == '(' && s[y] == ')') || (s[x] == '[' && s[y] == ']'))
- dp[x][y] = dfs(x + 1,y - 1) + 2;
- for (int i = x;i <= y - 1;i++)
- dp[x][y] = max(dp[x][y],dfs(x,i) + dfs(i + 1,y));
- return dp[x][y];
- }
- int main()
- {
- while (scanf("%s",s + 1)> 0)
- {
- memset(dp,-1,sizeof(dp));
- if (s[1] == 'e')
- break;
- int len = strlen(s + 1);
- printf("%d\n",dfs(1,len));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3323093.html