动态规划:添加最少括号数问题Java
时间: 2023-07-08 19:22:43 浏览: 39
动态规划可以解决添加最少括号数问题,具体思路如下:
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;
}
```