解题思路

这是经典的区间动态规划。设字符串为 $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]$ ：

dfs(l,r)=\min_{l<i\le r}\bigl(dfs(l+1,i-1)+\mathrm{cost}(s[l],s[i])+dfs(i+1,r)\bigr)

题目内容

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

选择提交后点击「开始AI分析」