dfs

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
string s;
int dp[105][105];
bool check(char a,char b)
{
	if(a=='('&&b==')'||a=='['&&b==']')
		return true;
	return false;
}
int dfs(int l,int r)
{
	if(l>r)
		return 0;		
	if(dp[l][r])
		return dp[l][r];		
	if(l==r)
		return dp[l][r]=1;
	dp[l][r]=100;
	for(int i=l;i<r;i++)
		dp[l][r]=min(dp[l][r],dfs(l,i)+dfs(i+1,r));
	if(check(s[l],s[r]))
		dp[l][r]=min(dp[l][r],dfs(l+1,r-1));	
	return dp[l][r];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>s;
	s=" "+s;
	cout<<dfs(1,s.size()-1)<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
string s;
int n;
// dp[i][j] s[i]~s[j] 这个子串最少加几个字符变成合法的
// 所有长度为0的区间，初始需要的步数都是0
int dp[105][105];
bool check(char a, char b)
{
    return (a == '(' && b == ')') ||
           (a == '[' && b == ']');
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    n = s.length();
    s = " " + s; // 现在的每个字符是 s[1]~s[n]
    for (int len = 1; len <= n; len++)
    {
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            // 计算 dp[l][r];
            if (len == 1)
            {
                dp[l][r] = 1;
                continue;
            }
            dp[l][r] = 100;
            for (int k = l; k <= r - 1; k++)
            {
                // s[l]~s[k], s[k+1]~s[r]
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
            }
            if (check(s[l], s[r]))
                dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
        }
    }
    cout<<dp[1][n];
    return 0;
}