poj 2955 Brackets 区间dp

?

题目大意是给你一个字符串，字符串由中括号和小括号组成，问该串里的最长的一个符合数学括号匹配规范的子序列是多长。

一开始打算用传说中的左闭右开区间来写，后来发现果然不适合我，还是换回左闭右闭区间写了。

dp的思路比较简单，dp[i][j] 表示从 i 到 j 的串种符合括号匹配的最长子序列。对于任意一个区间均可以存在一个点k (i <= k < j) 把区间分成 [i, k] 和 [k+1, j] 两部分。

所以得转移方程： dp[i][j] = max (dp[i][k] + dp[k+1][j])

另外，如果 i 和 j 的括号匹配的话,这里又多了一种情况，即 dp[i][j] = max (dp[i-1][j+1] + 2)

然后记忆化就行了。(感觉这种题目还是要记忆化更有感觉)

?

?

#include 
  
   
#include 
   
     #include 
    
      using namespace std; string a; int dp[101][101]; bool judge(char a, char b) { if (a == '(' && b == ')') return true; if (a == '[' && b == ']') return true; return false; } int DP(int l, int r) { if (dp[l][r] != -1) { return dp[l][r]; }www.2cto.com if (l == r) { return dp[l][r] = 0; } int tmp = 0; for (int k=l; k
     
      > a) { if (a == end) break; memset(dp, -1, sizeof(dp)); int ans = DP(0, a.size()-1); cout << ans << endl; } return 0; }
     
    
   
  

?