力扣HOT100之动态规划：32. 最长有效括号

这道题放在动态规划里属实是有点难为人了，感觉用动态规划来做反而更难理解了，这道题用索引栈来做相当好理解，这里先讲下索引栈的思路。

索引栈做法

我们定义一个存放整数的栈，定义一个全局变量result来记录最长有效子串的长度，然后我们通过下标来遍历整个字符串s，当我们遇到(时，就将其索引压入栈中，当我们遇到)且栈顶元素对应(时，此时遇到了一对闭合的括号，我们直接将栈顶的(弹出，再用当前元素的下标i减去当前栈顶元素的下标，就能得到当前有效字串的长度，若我们遇到)但是栈顶元素不是(时，说明还没匹配上，直接将当前元素的下标压入栈中。值得注意的是，当我们遇到一对匹配的括号，并将栈顶元素弹出后，如果此时栈为空，则说明从开头到现在的元素组成的子串都是有效合法的，这里为什么不能计算当前元素与栈顶元素下标之差？因为我们无法保证当前的栈是第一次被清空，如果是第一次被清空，则可以这么做，但如果是第4次被清空，直接用元素与栈顶元素下标之差得到的是第4小段合法子串的长度，正确的结果应当是4小段拼接起来的长度，因此这里要直接使用当前元素的下标+1来计算结果。

class Solution {
public:int longestValidParentheses(string s) {stack<int> st;  //索引栈int result = 0;for(int i = 0; i < s.size(); i++){if(!st.empty() && s[st.top()] == '(' && s[i] == ')'){  //遇到一对匹配的括号st.pop();   //将匹配上的'('弹出if(st.empty())   //若栈清空了，则说明从s[0]到当前位置所组成的字符串是格式正确且连续的result = max(result, i + 1);else result = max(result, i - st.top());  //若栈还没清空，则说明只是局部匹配，仅记录最外层左右括号之间的索引之差}else st.push(i);}return result;}
};

动态规划做法

感觉动态规划在状态转移的时候晦涩难懂，感觉自己想根本想不到，我是参考了一下这个大佬的题解才慢慢想明白的。建议先去看一下他的题解。接下来我们开始动规五部曲。
1.确定dp[i]的含义：以下标为i的元素结尾的情况下所能取到的最长有效子串的长度
2.确定递推公式
(1)当s[i] == '('时，dp[i] = 0;
(2)当s[i] == ')'且s[i - 1] == '('时，dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;
(3)当s[i] == ')'但s[i - 1] == ‘)‘时，先判断s[i - dp[i - 1] -1]是否为’(’
如果是，当i - dp[i - 1] - 2 >= 0时，则dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
否则dp[i] = dp[i - 1] + 2;
3.dp数组初始化 dp[0] = 0;
4.确定遍历顺序：从左往右遍历
5.打印数组(省略)
这里重点解释下递归公式。

1. 当我们以(结尾时，无论前面的字符串是否闭合，这个字符串一定闭合不了，所以dp[i]赋值为0毫无疑问。
2. 当我们以)结尾时，如果上一个字符为(，则我们遇到了形如......()的情况，我们先判断(前是否还有字符，如果有，则dp[i] = dp[i - 2] + 2;，如果没有，则dp[i] = 2，这也很好理解。
3. 当我们以)结尾时，如果上一个字符为)，则我们遇到了形如......))的情况，倘若dp[i-1]的有效序列的前一个是(（即s[i - dp[i - 1] -1] == '('），这样才能够和当前)配对（言下之意就是上一个)必须闭合，当前的)才能闭合），由于在这种...((...))情况下dp[i - 1]一定会小于dp[i]，我们还需要考虑与当前括号匹配的前面是否还有字符，若还有字符，则dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];，否则dp[i] = dp[i - 1] + 2;
   感觉第三种情况特别难想，好烧脑。。。

class Solution {
public:int longestValidParentheses(string s) {//1.确定dp[i]的含义：以下标为i的元素结尾的情况下所能取到的最长有效子串的长度//2.确定递推公式  //(1)当s[i] == '('时，dp[i] = 0;//(2)当s[i] == ')'且s[i - 1] == '('时，dp[i] = dp[i - 2] + 2;//(3)当s[i] == ')'但s[i - 1] == ')'时，先判断s[i - dp[i - 1] -1]是否为'('//如果是，当i - dp[i - 1] - 2 >= 0时，则dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]//否则dp[i] = dp[i - 1] + 2;//3.dp数组初始化 dp[0] = 0;//4.确定遍历顺序：从左往右遍历//5.打印数组(省略)int result = 0;vector<int> dp(s.size(), 0);for(int i = 1; i < s.size(); i++){if(s[i] == '(')  //以'('结尾一定闭合不了dp[i] = 0;else if(s[i] == ')'){if(s[i - 1] == '(')  //遇到一对'(' ')'，括号闭合dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;else{   //遇到')'')'if(i - dp[i - 1] > 0 && s[i - dp[i - 1] -1] == '('){  //遇到"((.....))"if(i - dp[i - 1] - 2 >= 0)dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];else dp[i] = dp[i - 1] + 2;}}}result = max(dp[i], result);}return result;}
};