Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

思路：动态规划思想，括号匹配发生在当前字符s[i]=')'时.

动态规划dp[i]表示以第i个字符为结尾能得到的括号匹配数。

那么在s[i]=')'时发生转移，分两种情况。如果s[i-1]='('那么dp[i]=dp[i-2]+2

如果s[i-1]=')' 并且s[i-dp[i-1]-1]='(' 那么dp[i]=dp[i-dp[i-1]-2] + dp[i-1] + 2

在dp[i]中取最大的即为答案。

注意边界。

代码如下

class Solution {public:    int longestValidParentheses(string s) {        stack 
    
      st;        int ans = 0;        int tmp = 0;        vector
     
       dp(s.size());                for (int i = 1; i < s.size(); ++i) {            if (s[i] == ')') {                if (s[i-1] == '(') {                    if (i == 1) dp[i] = 2;                    else dp[i] = dp[i-2] + 2;                }                else {                    if (i < 1) continue;                    int id = i - dp[i-1] - 1;                    if (id >=0  && s[id] == '(') {                        dp[i] = dp[i-1] + 2;                        if (id >= 1) dp[i] += dp[id-1];                    }                }            }            ans = max(dp[i], ans);        }        return ans;    }};