C 解法, 执行用时: 2ms, 内存消耗: 308KB, 提交时间: 2022-05-08

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int findmin(int a, int b) {
    if (a < b)
        return a;
    return b;
}
int main() {
    char c[101];
    gets(c);
    int h = strlen(c);
    int d[h][h];
    memset(d, 0, sizeof(d));
    for (int i = 0; i < h; i++) {
        d[i][i] = 1;
    }
    int min;
    for (int i = 1; i < h; i++) {
        for (int j = 0; j < h - i; j++) {
            if ( (c[j] == '(' && c[j + i] == ')') || (c[j] == '[' && c[j + i] == ']')) {
                min = d[j + 1][j + i - 1];
            } else {
                min = 52236;
            }
            for (int k = j; k < j + i; k++) {
                min = findmin(min, d[j][k] + d[k + 1][j + i]);
            }
            d[j][j + i] = min;
        }
    }
    printf("%d", d[0][h - 1]);
    return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 332KB, 提交时间: 2022-06-22

#include <stdio.h>

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

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

int main() {
    char s[101] = "";
    scanf("%s", 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 = i; j < sLen; j++) {
            dp[i][j] = j - i + 1;
        }
    }
    
    for (int d = 1; d < sLen; d++) {
        for (int i = 0; i < sLen - d; i++) {
            if ((s[i] == '(' && s[i+d] == ')') 
                ||
                (s[i] == '[' && s[i+d] == ']')) {
                
                if (i + 1 > i + d - 1) {
                    dp[i][i+d] = 0;
                } else {
                    dp[i][i+d] = dp[i+1][i+d-1];
                }
            } else {
                dp[i][i+d] = d + 1;
            }
            
            for (int k = i; k < i+d; k++) {
                dp[i][i+d] = min(dp[i][i+d], dp[i][k] + dp[k+1][i+d]);
            }
        }
    }
    
    printf("%d", dp[0][sLen - 1]);
    
    
    for (int i = 0; i < sLen; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return 0;
}

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

#include <iostream>
using namespace std;
#define MAX_N 105

int dp[MAX_N][MAX_N];//dp[i][j]表示区间i到j之间的最少插入的括号数
//输出dp[0][n-1]

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

int main()
{
    string s;
    cin>>s;
    int n = s.size();
    // 初始化 dp
    for(int i = 0; i < n; i++)
        dp[i][i] = 1;
    
    for (int l = 2; l <= n; l++) {
        for (int i = 0, I = n + 1 - l; i < I; i++) {
            int j = i + l - 1;
            dp[i][j] = 200;
            
            if (is_match(s[i],s[j]))
                dp[i][j] = dp[i + 1][j - 1];
            
            for (int k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
        }
    }
    cout << dp[0][n-1];
    return 0;
}

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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int findmin(int a, int b) {
    if(a<b) return a;
    return b;
}
int main() {
    char cn[101];
    gets(cn);
    int len = strlen(cn);
    int dp[len][len];
    memset(dp, 0, sizeof(dp));
    for(int i=0; i<len; i++) {
        dp[i][i] = 1;
    }
    int min;
    for(int i=1; i<len; i++) {
        for(int j=0; j<len-i; j++) {
            if( (cn[j] == '(' && cn[j+i] == ')') || (cn[j] == '[' && cn[j+i] == ']')) {
                min = dp[j+1][j+i-1];
            }
            else {
                min = 52236;
            }
            for(int k=j; k<j+i; k++) {
                min = findmin(min, dp[j][k] + dp[k+1][j+i]);
            }
            dp[j][j+i] = min;
        }
    }
    printf("%d",dp[0][len-1]);
    return 0;
}

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

#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
string s;
int match(int x, int y){
    if((s[x] == '[' && s[y] == ']') || (s[x] == '(' && s[y] == ')'))
        return 0;
    else return 2;
}
int main(){
    cin>>s;
    int len = s.size();
    for(int i = 0; i < len; ++i) dp[i][i] = 1;
    for(int ln = 2; ln <= len; ++ln){
        for(int i = 0; i < len; ++i){
            int j = i + ln - 1 ;
            if(j >= len) break;
            dp[i][j] = dp[i+1][j-1] + match(i, j);
            for(int k = i; k < j; ++k){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
    }
    cout<<dp[0][s.size()-1]<<endl;
    return 0;
}