32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
示例 2：

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”

感觉动态规划的题，核心就是找到状态转移的方差，一个是定义dp[i]，一个是如何根据之前的结果推理出dp[i]的表达式。

对于数组的题目，dp[i]的定义很多都是以i结尾的最优解是啥，然后再推理dp[i]的表达式。

对于这题，我们定义dp[i]表示以i结尾的最长有效括号的子串长度。

根据题意，我们假设：

  • 当s[i] = '('时，dp[i]必然等于0，因此不必讨论。

  • 当s[i] = ')'时：

    • 如果s[i-1] = '('，那么s[i]就必定和s[i - 1]配对，那么很容易得出这种情况的表达式：dp[i] = dp[i - 2] + 2
    • 如果s[i-1] = ')'，dp[i-1]表示以s[i - 1]结尾的最长有效括号子串，那么s[i]有可能和s[i - dp[i - 1] - 1]这个字符匹配，即如果s[i - dp[i - 1] - 1]为(，那么可以得到dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int longestValidParentheses(String s) {
        // dp[i]表示以i结尾的最长有效括号
        // 若s[i]为(，dp[i] = 0
        // 若s[i]为)，
        //     s[i-1]为(，那么dp[i] = dp[i - 2] + 2
        //     s[i-1]为)，并且s[i - dp[i-1] - 1]为(，那么dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2];
        int ans = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; 
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                ans = Math.max(ans, dp[i]);
            } 
        }
        return ans;
    }
}