解题思路

这是经典的区间动态规划。设字符串为 $s$，长度为 $n$。令 $dfs(l,r)$ 表示把子串 $s[l..r]$ 改成合法配方的最少修改次数。

空区间代价为 $0$。对非空区间，枚举与位置 $l$ 配对的右端点 $i$（$l<i\le r$），把 $s[l]$ 与 $s[i]$ 配成一对括号，再分别处理内部 $s[l+1..i-1]$ 与右侧 $s[i+1..r]$：

题目内容

一份配方由四类括号字符组成：( 与 )、[ 与 ]、{ 与 }、< 与 >。称一个字符串为合法配方，当且仅当它满足下列规则之一：

1. 它是空串；
2. 它由两段合法配方依次拼接而成；
3. 它由一对互相匹配的括号包住一段合法配方，匹配关系为 ( 配 )、[ 配 ]、{ 配 }、< 配 >。

每次操作可以将串中任意一个字符改成上述八种括号中的另一种。请计算使整个字符串变成合法配方所需的最少修改次数。

约束：字符串长度不超过 200，且保证长度为偶数。

输入描述

一行，由字符 (、)、[、]、{、}、<、> 组成的字符串。保证长度为偶数且不超过 200。

输出描述

输出一个整数，表示最少修改次数。

样例1

输入

()

输出

0

说明

() 本身已是一对匹配括号，无需修改。这是已经合法的边界情形，答案为 0。

样例2

输入

><

输出

2

说明

> 不是左括号，< 不是右括号，把它们配成一对需要改两下（例如改成 <>）。 答案为 2。