会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员，或
购买
该题目所属题库
，可解锁完整内容。
解题思路
这是经典的区间动态规划。设字符串为 s，长度为 n。令 dfs(l,r) 表示把子串 s[l..r] 改成合法配方的最少修改次数。
空区间代价为 0。对非空区间，枚举与位置 l 配对的右端点 i（l<i≤r），把 s[l] 与 s[i] 配成一对括号，再分别处理内部 s[l+1..i−1] 与右侧 s[i+1..r]：
dfs(l,r)=l<i≤rmin(dfs(l+1,i−1)+cost(s[l],s[i])+dfs(i+1,r))
