题解 | 括号区间匹配

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  思路来自昨天写的【染色问题】（https://gw-c.nowcoder.com/api/sparta/jump/link?link=https%3A%2F%2Fwww.nowcoder.com%2Fpractice%2F512619bee5874e85bd2812a0c9066125%3FchannelPut%3Dw25springcamp）
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
/*int finans = 0; 失败于“([([])]”
string s;
int rfind (string& ss, char c, int index){
  for (; index >= 0; index--){
    if (ss[index] == c) break;
  }
  return index;
}
void solve(int l, int r){
  if (l > r) return;
  if (s[l] == ')') {
    finans++;
    solve(l + 1, r);
  }
  else if (s[l] == ']'){
    finans++;
    solve(l + 1, r);
  }
  else if (s[l] == '('){
    int next = rfind(s, ')', r);
    if (next < l || next == -1) {
      finans++;
      solve(l + 1, r);
    }
    else{
      solve(l + 1, next - 1);
      solve(next + 1, r);
    }
  }
  else{
    int next = rfind(s, ']', r);
    if (next < l || next == -1){
      finans++;
      solve(l + 1, r);
    }
    else{
      solve(l + 1, next - 1);
      solve(next + 1, r);
    }
  }
}
int main() {
  cin >> s;
  size_t size = s.size();
  solve(0, size - 1);
  cout << finans;
}
// 64 位输出请用 printf("%lld")*/
char dp[110][110]{ 0 };//----------最多只有100个括号，dp【i】【j】表示索引i~j区间中需要添加的最少括号
int main() {
  string s;
  cin >> s;
  size_t size = s.size();
  for (int len = 1; len <= size; len++) {//---------从小到大枚举长度
    for (int i = 0; i < size; i++) {
      int j = i + len - 1;
      if (j >= size) break;
      if (i == j) dp[i][j] = 1;//----------只有一个括号必须要补
      else {
        dp[i][j] = 110;
        if (s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']') {//----如果匹配
          if (i == j - 1) dp[i][j] = 0;//--------修正一个括号时的‘1’
          else dp[i][j] = dp[i + 1][j - 1];
        }
        for (int k = i; k < j; k++) dp[i][j] = min(static_cast<int>(dp[i][j]), static_cast<int>(dp[i][k] + dp[k + 1][j]));//----------这里注意就算匹配成功也要枚举避免样例“[])[[)]”的答案从3变成5
      }
    }
  }
  cout << static_cast<int>(dp[0][size - 1]);//----------记得类型转换
  return 0;
}