动态规划：添加最少括号数问题java

动态规划可以解决添加最少括号数问题，具体思路如下：

1. 定义状态：使用一个一维数组 dp[i] 表示到第 i 个字符为止，所需添加的最少括号数。

2. 初始化状态：dp[0] = 0，即字符串为空时不需要添加任何括号。

3. 状态转移方程：

（1）如果 s[i] 是左括号，则 dp[i] = dp[i-1] + 1，因为需要添加一个右括号与之匹配；

（2）如果 s[i] 是右括号，则需找到与之匹配的左括号，设其下标为 j，则 dp[i] = dp[j-1] + i - j + 1，其中 dp[j-1] 表示左括号之前的最少添加括号数，i - j + 1 表示匹配的左右括号数目。

4. 最终状态：dp[n-1]，即到字符串末尾时所需添加的最少括号数。

Java代码实现如下：

public int minAddToMakeValid(String s) {
    int n = s.length();
    int[] dp = new int[n];
    dp[0] = 0;
    int ans = 0;
    for (int i = 1; i < n; i++) {
        if (s.charAt(i) == '(') {
            dp[i] = dp[i-1] + 1;
        } else {
            int j = i - dp[i-1] - 1;
            if (j >= 0 && s.charAt(j) == '(') {
                dp[i] = dp[j-1] + i - j + 1;
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}