C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-04-18

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int match(string s) {
        // write code here
        int len=s.size();
        vector<vector<int>>dp(len,vector<int>(len));
        for(int i=len-1;i>=0;i--){
            dp[i][i]=1;
            for(int j=i+1;j<len;j++){
                if(s[i]=='(' && s[j]==')' || (s[i]=='[' && s[j]==']')){
                    dp[i][j]=dp[i+1][j-1];
                }else{
                    dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
                }
                for(int k=i+1;k<j;k++){
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
            }
        }
        return dp[0][len-1];
    }
};

C 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-06-23

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

int min(int a, int b) {
    return a > b ? b : a;
}

int match(char* s ) {
    int sLen = strlen(s);
    int **dp = (int **)malloc(sizeof(int *) * sLen);
    for (int i = 0; i < sLen; i++) {
        dp[i] = (int *)malloc(sizeof(int) * sLen);
        for (int j = 0; j < sLen; j++) {
            dp[i][j] = 101;
        }
        dp[i][i] = 1;
    }
    
    for (int d = 1; d < sLen; d++) {
        for (int i = 0; i < sLen - d; i++) {
            int left = i, right = i + d;
            
            if ((s[left] == '(' && s[right] == ')')
                ||
                (s[left] == '[' && s[right] == ']')) {
                if (d == 1) {
                    dp[left][right] = 0;
                } else {
                    dp[left][right] = dp[left+1][right-1];
                }
            }
            
            for (int k = 0; k < d; k++) {
                dp[left][right] = min(dp[left][right], dp[left][left+k] + dp[left+k+1][right]);
            }
        }
    }
    
    int result = dp[0][sLen-1];
    
    for (int i = 0; i < sLen; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-06-21

class Solution {
  public:
    int match(string s) {
        int h = s.size();
        vector<vector<int>>a(h, vector<int>(h));

        for (int i = h - 1; i >= 0; i--) {
            a[i][i] = 1;
            for (int j = i + 1; j < h; j++) {
                if (s[i] == '(' && s[j] == ')' || (s[i] == '[' && s[j] == ']')) {
                    a[i][j] = a[i + 1][j - 1];
                } else {
                    a[i][j] = min(a[i + 1][j], a[i][j - 1]) + 1;
                }
                for (int k = i + 1; k < j; k++) {
                    a[i][j] = min(a[i][j], a[i][k] + a[k + 1][j]);
                }
            }
        }
        return a[0][h - 1];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 432KB, 提交时间: 2022-07-04

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int match(string s) {
        // write code here
        int length=(int)s.length();
        int** res=new int*[length];
        for(int i=0;i<length;i++) res[i]=new int[length];
        for(int i=0;i<length;i++) res[i][i]=1;
        for(int i=0;i<length-1;i++){
            if(s[i]=='('&&s[i+1]==')'||s[i]=='['&&s[i+1]==']')
                res[i][i+1]=0;
            else res[i][i+1]=2;
        }
        for(int i=length-2;i>=0;i--){
            for(int j=i+1;j<length;j++){
                res[i][j]=INT_MAX;
                res[i][j]=min(res[i+1][j]+1,res[i][j]);
                res[i][j]=min(res[i][j-1]+1,res[i][j]);
                if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']')
                    res[i][j]=min(res[i+1][j-1],res[i][j]);
                for(int k = i+1; k < j; ++k) {
                    res[i][j] = min(res[i][j], res[i][k] + res[k+1][j]);
                }
            }
        }
        return res[0][length-1];    
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 440KB, 提交时间: 2022-05-09

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int match(string s) {
        // write code here
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n));
        for(int i=n-1;i>=0;--i){
            dp[i][i]=1;
            for(int j=i+1;j<n;++j){
                if((s[i]=='('&&s[j]==')')||s[i]=='['&&s[j]==']'){
                    dp[i][j]=dp[i+1][j-1];
                }else{
                    dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
                }
                for(int k=i+1;k<j;++k){
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
            }
        }
        return dp[0][n-1];
    }
};