题解：由于要求的是字串，不是子序列，区间dp在这里不合适。考虑定义一个dp[i]表示以是s[i]为结尾的字串最长有效长度。分类讨论一下，当s[i]为"("的时候，dp[i] =0;
当s[i]为”)“的时候，考虑前一位，当s[i-1] == ‘(‘的时候 dp[i] = 2 + dp[i-2]; 当s[i-1] == ‘)‘的时候，看以s[i-1]为结尾的字串的前以为是不是‘(‘，是的话 dp[i] = 2+dp[i-1] + dp[i-dp[i-1]-2];
ac代码如下:
#include <iostream> #include <algorithm> #include <string> #include <cstring> using namespace std; int dp[100010]; int longestValidParentheses(string s) { int Len = s.length(); memset(dp,0,sizeof(dp)); int mx = -1; for(int i=1; i<Len; i++) { if(s[i] == ‘)‘) { if(s[i-1] == ‘(‘) { dp[i] = 2; if(i-2>=0) dp[i] += dp[i-2]; } else { if(s[i-dp[i-1]-1] == ‘(‘) { dp[i] = 2+dp[i-1]; if(i-dp[i-1]-2 >=0) dp[i] += dp[i-dp[i-1]-2]; } } } mx = max(dp[i],mx); } for(int i=0;i<Len;i++) cout << dp[i] <<" "; cout <<endl; return mx; } int main() { string s= "()(())"; cout << longestValidParentheses(s) <<endl; return 0; }
原文：https://www.cnblogs.com/z1141000271/p/12141612.html