动态规划-最长的括号子串

求解代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


public int longestValidParentheses(String s) {
        char[] str = s.toCharArray();
        int[] dp = new int[str.length];
        int ans = 0;
        for (int i = 1, p; i = 0 && str[p] == '(') {
                    dp[i] = dp[i - 1] + 2 + (p - 1 >= 0 ? dp[p - 1] : 0);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

小贴士

dp[i]是以字符串中第i个字符str[i]结尾的最长有效括号子串的长度。

因为有效括号子串一定是以)结尾到，以(结尾的子串不可能有效。

所以，只需要处理str[i] == ')'的情况，str[i] == '('时，让dp [i] = 0 即可。

根据定义dp[i-1]表示的是以str[i-1]结尾的最长有效括号长度，也就是说从i-dp[i-1]到i-1的这段子串是有效括号。

那么，要匹配当前的这个str[i] = ')'，左括号必须出现在从i-dp[i-1]到i-1的这段有效子串的前一个位置，这个位置就是p，即i - dp[i-1] - 1。

p指的是当前)能形成有效匹配的唯一可能的左括号位置。

状态转移方程的含义是：

以i结尾的最长有效长度 = 前一个位置(i-1)的有效长度 + 当前匹配的一对括号 + 左括号位置(p)左边（如果有）的有效长度。