本文共 1497 字，大约阅读时间需要 4 分钟。

题目：给一个长度n(<=100)的只包含'[',']','(',)'的字符串，求最长的完全匹配的子序列。输出长度

题解：区间dp，dp[i][j]表示i~j的最长匹配数，一支dp[i][k:i~j-1]，怎么更新dp[i][j]?

• 和几乎一样。只有s[k]=='('&&s[k]==')'或者s[k]=='['&&s[k]==')'时才可能更新（+一组），否则只需要无脑max(dp[i][j],dp[i][k]+dp[k+1][j])。
• 抓住关键：小区间更新大区间

代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int N = 1e2 + 10;int n, dp[N][N];char s[N];signed main() {    while (scanf("%s", s + 1) != EOF) {        if (s[1] == 'e') break;        n = strlen(s + 1);        int len, i, j, k;        memset(dp, 0, sizeof(dp));        // for (i = 1; i <= n; i++) dp[i][i] = 0;        for (len = 2; len <= n; len++) {            for (i = 1; i + len - 1 <= n; i++) {                j = i + len - 1;                for (k = i; k <= j - 1; k++) {                    if ((s[j] == ']' && s[k] == '[') ||                        (s[j] == ')' && s[k] == '('))                        dp[i][j] =                            max(dp[i][j], dp[i][max(i, k - 1)] +                                              dp[min(j - 1, k + 1)][j - 1] + 2);                    //+2是因为不是求的对数，而是个数                    // dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + 2);                    //以上代码是错的，因为本来就不和理i~k-1，k+1~j-1单独算，另外+2                    //而且还不一定得到更新，因为可能去掉k之后少了2，另加上2只是补了回来                    else                        dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);                }            }        }        cout << dp[1][n] << endl;    }    return 0;}
       
      
     
    
   

转载地址：https://blog.csdn.net/I_have_a_world/article/details/117657051 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！