Leetcode 32 Longest Valid Parentheses DP好题

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.

就喜欢做这种想法题，

一开始的想法和之前做过的一道括号匹配差不多，用栈。

https://cloud.tencent.com/developer/article/1019321

记录未匹配的括号位置，然后两两相减找到最大值，过了，但速度并不快。

在discuss中看到有人用DP，恍然大悟！

dpi表示以当前位置为终点的最长长度，则只能在）处更新，

如果s[i-1-dpi-1]=='('，则说明当前位置可以和i-1-dpi-1位置匹配，dpi=dpi-1+2;

然后还要加上匹配位置之前的最长长度dpi+=dp[i-dpi];

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