[动态规划]leetcode32：最长的有效括号(hard)

括号(hard)"/>

[动态规划]leetcode32：最长的有效括号(hard)

题目：

题解：

• 动态规划，dp[i]表示以i结尾的最长有效括号长度
• 当匹配到右括号时，我们需要尝试向前匹配左括号，如果是左括号，则要更新匹配长度

代码如下：

class Solution {
public://题解：动态规划，dp[i]表示以i结尾的最长有效括号长度int longestValidParentheses(string s) {if(s.empty())return 0;int n=s.size();int dp[n];memset(dp,0,sizeof(dp));for(int i=1;i<n;++i){if(s[i]==')')//当匹配为右括号时，尝试向前匹配左括号{int pre=i-dp[i-1]-1;//pre的位置需要减去前一个有效括号长度，还有减1，才能到达未匹配的括号if(pre>=0&&s[pre]=='(')//如果是左括号，则更新匹配长度{dp[i]=dp[i-1]+2;//长度加2，表示左右两个括号匹配好了if(pre>0)//处理独立的括号对，比如()(),()(()){dp[i]+=dp[pre-1];}}}}return *max_element(dp,dp+n);}
};