LeetCode32.最长有效括号和这个题比较类似，但那道题可以用一维的线性dp, dp[i]表示以str[i]结尾（str[i]必须参与到以它结尾的最长有效括号中）的最长有效括号数, 而这个题的dp[l][r]表示以l, r为左右端点内的所有有效括号形式的数量（可以不连续，所以要每一次都要dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r])）

Acwing.1070:

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int dp[N][N];
char str[N];

bool isMatch(char a, char b){
    if((a == '(' && b == ')') || (a == '[' && b == ']'))    return true;
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> str + 1;
    int Len = strlen(str + 1);
    for(int len = 1; len <= Len; len++){
        for(int l = 1; l + len - 1 <= Len; l++){
            int r = l + len - 1;
            if(len == 1)    dp[l][r] = 0;
            else if(isMatch(str[l], str[r]))    dp[l][r] = max(dp[l][r], dp[l + 1][r - 1] + 2);
            else    dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
            for(int k = l; k <= r; k++){
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r]);
            }
        }
    }
    cout << Len - dp[1][Len];
    return 0;
}

LeetCode.32:

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0;
        int dp[30001];
        memset(dp, 0, sizeof dp);
        for(int i = 1; i < s.size(); i++){
            if(s[i] == ')'){
                if(s[i - 1] == '(') dp[i] = (i - 2 >= 0 ? dp[i - 2] + 2 : 2);
                else{
                    int j = i - dp[i - 1] - 1;
                    if(j >= 0 && s[j] == '('){
                        dp[i] = dp[i - 1] + 2;
                        if(j >= 1)  dp[i] += dp[j - 1];
                    } 
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};