vlambda博客
学习文章列表

 动态规划系列专题   LeetCode32

在之前我们也推送过很多动态规划系列的题目，但由于动态规划作为算法界的扛把子真的很难，因此我们今后会陆续推送多期动态规划专题题目，挑选的题目大都属于中等偏上难度（也会有部分有代表性的较为简单的题目）。希望通过整理这类难题，能和大家一起将动态规划这块硬骨头啃下来！

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

2 题解

2.1 暴力扫描

可以使用计数法判断区间 的子串是否为有效括号，因此使用双重循环即可解决这个问题。

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int count = 0;
            int max_len = 0;
            for (int j = i; j < n; j++) {
                if (s[j] == '(') count++;
                else count--;
                if (count == 0) max_len = max(max_len, j - i + 1);
                if (count < 0) break;
            }
            ret = max(ret, max_len);
        }
        return ret;
    }
};

*上面的代码可以AC，时间复杂度 ，空间复杂度 。

2.2 动态规划

这道题的动态规划解法还真的不好想，在我自闭修炼了两天之后才真的领悟到了这道题😭。这个问题难就难在这个 它应该代表什么意思，可能很多人会和我一样将 看作前 个括号子串能够求得的最长有效括号数量，如果这么想的话你就会——自闭（嗯没错）。

应该用来表示以第 个括号作为字符串结尾的最长有效字符串的长度，嗯大概就是这样了。因此如果 为  ( 那么 就为0了，因为一个合法的有小括号最后一位一定为 )。接下来就需要从左往右遍历字符串，会有如下两种情况，我们取其大：

• s[i]=')' 且 s[i-1]='(' : 这种情况比较直观，如果当前位置 i 的括号为右括号，且前一个括号为左括号，那么就在 的基础上多了一对匹配括号，因此得到 ；

• s[i]=')' 且 s[i-1-dp[i-1]]='(' : 这种情况不是很好理解，举个栗子如下图所示，当考虑到下标为5的括号 )时，显然位置5和位置2的两个括号可以成为一对，至此从位置2到位置5的括号都能够成双成对，因此有 。这时候还需要考虑能不能再和更前面的括号继续联姻，因此需要再加上 ，最终得到：

至此状态转移方程就介绍完了，如果你觉得上面的解释仍然不够直观，建议自己参照下图画一下图，就能够明白上面的逻辑了。

提供拙劣的代码如下：

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int ret = 0;
        vector<int> dp(n, 0);
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(')
                    dp[i] = max(dp[i], dp[i - 1] + 2);
                if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                    int base = i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2]: 0;
                    dp[i] = max(dp[i], dp[i - 1] + base + 2);
                }
                    
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

*上面的代码可以AC，时间复杂度 ，空间复杂度 。

2.3 栈

看完前面的动态规划解法我已经神魂颠倒了，然鹅还有更加厉害的借助栈的方法orz，官方题解[1]已经解释的很清楚了，暂时就不写了~

*参考链接

[1] https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode/