浮云出处元无定
得似浮云也自由
C++，dp，字符串。这道题也有不用dp的解法，但是这种奇技淫巧并不通用，到面试的时候很难想起来，还是老老实实把dp理解好，能够解很多题目。
本题目如果用动态规划，重点是把括号匹配的关系理清楚：
(在前，)在后- 如果
(和)之间是(...)且(...)是有效括号序列，那么...一定由0到多个不定长度的有效括号序列组成
理清括号匹配的关系后，再思考怎么用dp去套。。。
显然，我们可以用dp[i][j] == true来表示[i, j]是有效括号序列，但实际上不用二维数组，一维就够了，dp[i][j] == true记录了两个信息
i到j的长度，即j - i + 1i到j之间，符合有效括号序列
这两个信息，用一维数组即可记录，dp[i] = n，表示以i为结尾的长为n的有效括号序列。那么当碰到某个字符是)的时候，需要找到与之匹配且没有被匹配的(：
dp[i - 1]记录的就是以i为结尾的长为n的最长有效括号序列i - dp[i - 1] - 1就是与之匹配且没有被匹配的(所在的位置
所以长度就是：dp[i] = (i - j + 1) + ((j - 1) >= 0 ? dp[j - 1] : 0)
代码也是很简短：
class Solution {
public:
int longestValidParentheses(string s) {
int ans = 0;
vector<int> dp(s.length(), 0);
for (int i = 1; i < s.length (); i++) {
if (s[i] == ')') {
int j = i - dp[i - 1] - 1;
if (j >= 0 && s[j] == '(')
dp[i] = (i - j + 1) + ((j - 1) >= 0 ? dp[j - 1] : 0);
}
ans = max(ans, dp[i]);
}
return ans;
}
};
