【c++】【leetcode32】最长有效括号（动态规划）

最长有效括号

用动态规划来做，dp[i]表示以第i个结尾的最长有效括号，因此以'('结尾的都为0。
如何去计算以')'结尾的dp[i]值？

• 如果s[i-1] = '(',dp[i] = dp[i-2] + 2
• 如果s[i-1] = ')'，此时要判断 ')'是否合理，如果不合理，dp[i]=0,如果合理，前一个合理的最长的前一个必然是'('，此时dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2];。

注意数组可能越界的问题
时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( n ) O(n) O(n)

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