fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool is_match(char a, char b) {
  5.     return (a == '(' && b == ')') ||
  6.            (a == '[' && b == ']') ||
  7.            (a == '{' && b == '}');}
  8.  
  9. int main() {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(NULL);
  12.     string s;
  13.     cin >> s;
  14.     int n = s.length();
  15.     vector<vector<int>> dp(n, vector<int>(n, 0));
  16.  
  17.     for (int len = 1; len <= n; ++len) {
  18.         for (int i = 0; i + len - 1 < n; ++i) {
  19.             int j = i + len - 1;
  20.             if (i == j) {
  21.                 dp[i][j] = 1;
  22.             } else {
  23.                 dp[i][j] = 1e9;
  24.                 if (is_match(s[i], s[j])) {
  25.                     dp[i][j] = dp[i + 1][j - 1];
  26.                 }
  27.                 for (int k = i; k < j; ++k) {
  28.                     dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
  29.                 }
  30.             }
  31.         }
  32.     }
  33.     cout << dp[0][n - 1] << endl;
  34.     return 0;
  35. }
  36.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
(])({(})(
stdout
copy 
3
https://ideone.com/bmVVLB
language:
C++ (gcc 8.3)
created:
20 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!