为了提高对动态规划的理解，我专门做了LeetCode上一些动态规划的题目，记录一下他人的思路和代码。
题目描述
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
栈解法
感谢kevin的思路。
首先，看到这题需要判断合法的括号对，很直接就能想到用栈的数据结构去实现。扫描字符串，若当前字符是’(‘则进栈，是’)’就判断栈顶元素是否存在且为’)’，若不符合则该字符串非法。
但是，这道题问的是最长有效括号的长度，所以我们的栈元素就用pair<char, int>实现，char对应当前字符，int对应当前字符的索引。在每次出栈时，用(当前索引 - 出栈元素索引 + 1)即可计算长度。
上面这种解法能够解决诸如”()”, “(())”一类的案例，但是还不够。比方说，如果遇到了”()()”的情况就没有办法了。因为除了当前的合法括号对长度以外，我们还需要把前面连续的合法括号对长度也算进去啊，但是之前的合法括号对已经出栈了，应该怎么处理呢。
我们可以从这个案例”)()()”出发来考虑。假设这里的五个字符，对应的索引分别为1,2,3,4,5. 第1个字符没有和它配对的括号，因此不合法。接着，后续的4个字符依次进栈、出栈x2、进栈、出栈x2. 这时我们发现，最长有效括号长度正好就是(当前索引 - 栈顶元素索引) = 5 - 1 = 4，这不是巧合。由于前面连续的合法括号对都已经出栈了，所以此时的栈顶元素对应的索引恰恰就是当前最长有效子串的起始点，这就是解决该问题的关键之处。
解决了关键点，后面的设计就水到渠成了。我们固定栈底元素为可能的最长有效括号串的开头，初始化为pair(‘b’, 0).当遇到括号不合法的情况时（此时栈底元素正好也是栈顶元素），更新该栈底元素的索引为当前索引。其它的设计如上所述。
class Solution {
public:
int longestValidParentheses(string s) {
int ans = 0;
int idx = 0;
stack<pair<char, int>> sk;
sk.push(make_pair<char, int>('b', 0));
for (char c : s){
idx++;
if (c == '(')
sk.push(make_pair(c, idx));
else{
pair<char, int> p = sk.top();
if (p.first == '('){
sk.pop();
ans = max(ans, idx - sk.top().second);
}
else{
// 修改栈低元素的seond为当前字符串开头
assert(p.first == 'b');
sk.top().second = idx;
}
}
}
return ans;
}
};
动态规划解法
感谢powcai
我们用dp[i]表示以i结尾的最长有效括号,注意这里是以i结尾的，不是0到i最长有效括号。
-
当s[i]为(,dp[i]必然等于0,因为不可能组成有效的括号;
-
那么s[i] 为 )
当 s[i-1] 为 (，那么 dp[i] = dp[i-2] + 2；
当 s[i-1] 为 ) 并且 s[i-dp[i-1] - 1] 为 (，那么 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]；这是为了解决”(())”类情况。
时间复杂度：O(n)
class Solution {
def longestValidParentheses(self, s: str) -> int:
n = len(s)
if n == 0: return 0
dp = [0] * n
res = 0
for i in range(n):
if i>0 and s[i] == ")":
if s[i - 1] == "(":
dp[i] = dp[i - 2] + 2
elif s[i - 1] == ")" and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
if dp[i] > res:
res = dp[i]
return res
总结
栈解法循序渐进，从特殊到一般，渐渐找到题目的解法。动态规划，是要明白以i结尾，这一点与其它动态规划有一些区别，其次就是考虑到多种情况，给出相应的解决办法。