【LeetCode】最长有效括号 [H]（动态规划）

32. 最长有效括号 - 力扣（LeetCode）

一、题目

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

示例 1：

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

示例 2：​​​​​​​

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

示例 3：​​​​​​​

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

二、代码

class Solution {
    public int longestValidParentheses(String str) {
        if (str == null || str.length() < 2) {
            return 0;
        }
 
        char[] s = str.toCharArray();
        // dp[i] : 子串必须以i位置结尾的情况下，往左最远能扩出多长的有效区域
        // dp[0] = 0; （  ）
        int[] dp = new int[s.length];
        int ans = -1;
        int pre = 0;
        for (int i = 1; i < s.length; i++) {
            // 只有右括号可以讨论，左括号的话直接为0，因为右括号还有机会被左边的左括号调平，但是如果是左括号的话，永远都不可能被左边的括号调平
            if (s[i] == ')') {
                // 当前谁和i位置的)，去匹配
                pre = i - dp[i - 1] - 1; // 与str[i]配对的左括号的位置 pre
                // 如果pre并没有越界并且pre位置的字符是左括号，那么就说明i找到了何其配对的最括号
                if (pre >= 0 && s[pre] == '(') {
                    // 此时以i位置结尾的情况下，至少能向左扩dp[i-1]+2个长度，dp[i-1]是i和pre之间有效括号长度，2指的就是i和pre组成的两个括号长度
                    // 然后再去看pre左边的括号是否还能继续向左扩，如果可以扩就将左边的有效长度累加到dp[i]上，需要先判断pre>0，保证pre-1不会越界，如果pre已经到了0位置，那么左边就没有有效字符了。
                    dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
                }
            }
            // 取以i位置结尾的情况下最大的有效括号长度
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

三、解题思路 

必须以0位置结尾往左延伸多长能有效?

必须以1位置结尾往左延伸多长能有效?

必须以2位置结尾往左延伸多长能有效?

必须以每个位置结尾的情况下，往左延伸多长有效最长的有效长度,

每个位置结尾答案如果都能求出来，整体答案中最大值就是我们要的。

因为客观上来讲，最长的有效子串它必须以某个位置结尾，而我们求出来每一个结尾的答案。

把所有的答案中求max就是最后的答案。