动态规划：添加最少括号数问题Python代码

好的，下面是 Python 代码实现：

def minAddToMakeValid(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n-2, -1, -1):
        for j in range(i+1, n):
            if (s[i] == '(' and s[j] == ')') or (s[i] == '[' and s[j] == ']') or (s[i] == '{' and s[j] == '}'):
                dp[i][j] = dp[i+1][j-1]
            else:
                dp[i][j] = n
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
    return dp[0][n-1]

其中 dp[i][j] 表示字符串s[i:j+1] 需要添加的最少括号数，n 是字符串的长度。

我们从字符串的最后一个字符开始，向前遍历，依次计算 dp[i][j]。在计算 dp[i][j] 的时候，我们首先判断 s[i] 和 s[j] 是否可以匹配，如果可以匹配，则 dp[i][j] 等于 dp[i+1][j-1]，否则我们需要枚举中间位置 k，计算 dp[i][j] 的最小值，即：

dp[i][j] = min(dp[i][k] + dp[k+1][j]), i <= k < j

最终的答案就是 dp[0][n-1]，其中 n 是字符串的长度。