题解 | #括号区间匹配#

#动态规划简单求解
s=input()
lenth=len(s)
dp=[[0]*lenth for _ in range(lenth) ]
def match(a,b):
    if a=='(' and b==')':return True
    if a=='[' and b==']':return True
    return False
for i in range(len(dp)):#初始化区间长度为1时最少插入次数为1
    dp[i][i]=1
for part_len in range(2,lenth+1):
    for i in range(lenth-part_len+1):
        j=i+part_len-1
        dp[i][j]=float('inf')
        if match(s[i],s[j]):
            dp[i][j]=dp[i+1][j-1]
        for k in range(i,j):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])
print(dp[0][lenth-1])