题解 | #括号区间匹配#
括号区间匹配
https://www.nowcoder.com/practice/e391767d80d942d29e6095a935a5b96b
#动态规划简单求解
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])