题目：
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. (Hard)
分析：
题意是找到最长的合法括号字串。
看着就很想动态规划的题目，但是开始考虑的是dp[i][j]记录i到j是否是合法串。但是递推关系没法找。
想到应该是符合单序列动态规划的情况，用dp[i]表示以i结尾的最长合法括号串的长度。
递推关系如下：
如果 s[i] == '(' 则 dp[i] = 0;
如果 s[i] == ')' 则
如果 s[i - 1] == '(' 则 dp[i] = dp[i - 2] + 2;
如果 s[i - 1] == ')' 则需要记录 j = dp[i - 1]，并判断 s[i - 1 - j] 也就是从后往前数第一个不符合的字符的情况。
如果s[i - 1- j] == '(' 则 dp[i] = dp[i - j -2] + dp[i - 1] + 2； // i-j-2位置向前合法的，加上i-1位置向前合法的，加上s[i-j-1]和s[i]配对的2;
如果s[i - 1 - j]不存在或者为 ')' 则 s[i] = 0;
求出不等于0的dp[i]时更新result。
把上述递推关系实现代码如下：
class Solution {
public:
int longestValidParentheses(string s) {
if (s.size() == || s.size() == ) {
return ;
}
int result = ;
int dp[s.size()] = {};
if (s[] == ')' && s[] == '(') {
dp[] = ;
result = ;
}
for (int i = ; i < s.size(); ++i) {
if (s[i] == '(') {
dp[i] = ;
}
if (s[i] == ')') {
if (s[i - ] == '(') {
dp[i] = dp[i - ] + ;
result = max(result,dp[i]);
}
if (s[i - ] == ')') {
int j = dp[i - ];
if (i - j - >= && s[i - j - ] == '(') {
dp[i] = dp[i - ] + dp[i - j - ] + ;
result = max(result,dp[i]);
}
else {
dp[i] = ;
}
}
}
}
return result;
}
};