括号(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);}
};
更多推荐
[动态规划]leetcode32:最长的有效括号(hard)
发布评论