引言

这是一道LeetCode题目，用来对之前的一篇动态规划的文章进行进一步的实践说明

原题

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：s = ""
输出：0

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

动归思路

首先确定边界问题，负数不能访问，初始值应该为0，f(0)为0。

然后再思考动态转移公式，发现这道题并不是简单的一个公式就可以解决的，由于括号的匹配一定是由)结束，所以我们只考虑)的情况。总结出一下两种右括号出现的情况

  1. …….()
  2. …….))

第一种情况

第一种情况的状态转移公式比较容易写出，直接给出

1
2
f(i) = f(i-2)+2
i>1

在写状态转移公式的过程中我们要对减号比较敏感，当出现减号的时候我们就需要对操作数的大小进行判断，防止越界的发生

第二种情况

第二种情况的状态转移公式就比较难写，首先我们需要知道这个右括号是否在前面有与之对应的左括号，若无，f(i)=0，若有，进行计算。

那么怎么找到这个右括号对应的括号呢，因为第i-1个右括号记录了最长的有效长度，所以我们可以根据这个长度向前在延伸一位就能找到第i个括号对应的字符，表达出来就是

1
2
3
4
if(f(i-dp[i-1] - 1) != '('){
    pass
}
//这里也要注意判断i - dp[i - 1] - 1的正负性

接下来我们要思考的就是如果这个右括号对应了一个左括号要怎么写出这个状态转移公式。我们首先假设将第i-1位的有效长度加入进来写出公式

1
2
f(i) = f(i - 1) + 2
//i>1

但是这样的计算结果显然是错误的，因为我们遗漏了匹配到的左括号之前可能是有效的括号字符串，现在这个左括号被成功匹配之后两个有效字符串的长度应该进行相加，所以我们进一步得出正确的有效字符串长度公式

1
2
3
f(i) = f(i - 1) + 2 + f(i - dp[i - 1] - 2)
//这里的i - dp[i - 1] - 2可以理解为i - dp[i - 1] - 1 - 1即匹配到的左括号的再左边一位
//同时需要注意正负性的判断

这样我们就得到了一个完整的状态转移方程，最后只需要取动归数组中最大的值就是本题的答案，题目的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 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 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}