动态规划-括号间匹配

题目描述

给定一个由 '[' ，']'，'('，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。

例如当前串是 "([[])"，那么插入一个']'即可满足。

数据范围：字符串长度满足 1≤n≤100 

输入描述：

仅一行，输入一个字符串，字符串仅由 '[' ，']' ，'(' ，‘)’ 组成

输出描述：

输出最少插入多少个括号

分析：

（1）定义dp[i][j]为区间[i][j]需要插入的最少字符数

（2）初始化：

1. dp[i][j] = 1 如果i == j （步长为0）
2. dp[i][i+1] = 0 if match(s[i], s[i+1])， 否则 dp[i][i+1] = 2 （步长为1）

（3）状态转移：转移方向见下图（步长大于2时）

        dp[i][j]的值需要进行两步检查，最后取最小值：

        (1) 检查s[i],s[j]是否match

                Y=> dp[i][j] = dp[i+1][j-1] 

                N=> dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1 

        (2) 拆分区间[i,j]成两段

                dp[i][j] = dp[i][k] + dp[k+1][j]  (k>=i and k <j)

解答：

def match(c1, c2):
    if c1 == '(' and c2==')' or c1 =='[' and c2 == ']':
        return True
    return False

def solution(array):
    length = len(array)
    if length <= 1:
        return length

    dp = [[0]*length for _ in range(0, length)]
    # from (up,left)->(down, right)
    #           (direction)  
    #   1 2     / /   
    #     1 2  / /
    #       1 2 /
    #         1 2
    # dp[i][i+step], init 1: step=0, dp[i][i]=1
    for i in range(0, length):
        dp[i][i] = 1
    # dp[i][i+step], init 2: step=1, dp[i][i+1]= match? 0: 2
    for i in range(0, length-1):
        if match(array[i], array[i+1]):
            dp[i][i+1] = 0
        else:
            dp[i][i+1] = 2
    
    for i in range(2, length):
        for j in range(0, length):
            # [j][j+i] => j: line number; i: step length
            if j+i <= length-1:
                if match(array[j], array[j+i]):
                    dp[j][j+i] = dp[j+1][j+i-1]
                else:
                    dp[j][j+i] = min(dp[j+1][j+i], dp[j][j+i-1]) + 1
                # next step is to check when being splitted
                # e.g., "()....()", dp[i][j] = 12, then dp[i+1][j-1] = 10
                # however, dp[i][i+2] + dp[i+3][j] = 8
                for k in range(j+1, j+i):
                    dp[j][j+i] = min(dp[j][j+i], dp[j][k]+dp[k+1][j+i])
    # print(dp[0])
    return dp[0][length-1]

参考：括号区间匹配_牛客题霸_牛客网