【线性 dp】A015

一、Problem

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()"

二、Solution

这题最朴素的做法是枚举每一段子串，然后用栈检查每一段子串是否合法，并记录合法子串的长度，这种方法我试过，会超时…

方法一：栈 + dp

思路

如果当前字符 s[i] 为右括号 )，我们很容易想到要找到一个最近的左括号 ( 与之匹配，找最近的左括号 ( 可以用变量记录，但我们还要保存之前遇到的左括号 (，基于这一点我们要可用栈保存左括号的位置，最近的左括号就是栈顶元素

定义状态： $f[i]$ 表示位置 $i$ 之前的最长有效括号长度 思考初始化： $f[0:]=0$ 思考状态转移方程： $f[i]=f[j-1]+(i-j+1)（j是栈顶元素)$：表示如果 $i$ 位置是右括号 $($、$j$ 位置是最接近它的左括号，那么位置 $i$ 的长度就可以承接 $j-1$ 之前的长度， 思考输出：$max(f[0:])$ class Solution { public: int longestValidParentheses(string s) { int n = s.size(), ans = 0; stack<int> st; vector<int> f(n); for (int i = 0; i < n; i++) { if (s[i] == '(') st.push(i); else if (!st.empty()) { int j = st.top(), len = i-j+1; st.pop(); if (j > 0) f[i] = f[j-1] + len; else f[i] = len; if (f[i] > ans) ans = f[i]; } } return ans; } };

复杂度分析

时间复杂度：$O(n)$，空间复杂度：$O(n)$，

最近我都在用 C++ 做，真的很方便丫丫，大爱 C++

---

方法二：空间压缩

既然 dp 数组的值就是最长有效括号的长度，我们又知道有效括号的最小长度为 2，所以我们可以用索引 $i$ 减去 dp 的值来判断在 $i$ 位置前是否存在有效括号（i-dp[i-1] > 0 表示存在），这样可以把栈空间省去…

复杂度分析

时间复杂度：$O(n)$，空间复杂度：$O(n)$，