题目详情
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"
——题目难度:困难
题目所说的 “最长的包含有效括号的子串” 的意思是该子串里不允许有 没有成为"(...)"，也就是没有匹配的括号。 使用动态规划解题一般有如下3个步骤：
确定状态 - 研究最优策略的最后一步 - 化为子问题确定状态转移方程 - 根据子问题定义得到确定边界条件 和 初始情况接下来用以上3个步骤来分析题目： 1.确定状态：这里定义一个dp数组，dp[i]表示以下标 i 为字符结尾的最长有效字符串的长度(注意：这里是必须将s[i]这个字符包含在内的！) 2.确定状态转移方程：当遍历s串时，如果是s[i]='('，就不用考虑，因为不可能构造合法括号； 当s[i]=')'时，分以下两种情况： ①s[i-1]='('时，也就是字符串形如"...()"，那么dp[i] = dp[i-2] + 2 ②s[i-1]=')'时，也就是字符串形如"...))"的时候，这种情况下，如果前面要和 s[i] 组成有效括号对的字符，即形如"( (....) )"，这样的话，就要求 s[i - 1] 位置必然是有效的括号对，否则 s[i] 无法和前面对字符组成有效括号对。
如果倒数第二个')'是一个有效字符串(记为subs)，那么我们只需要判断 subs 前面的一个符号是不是'('，如果是'(' 则可以说明 此时的最长有效括号的长度为：subs 的长度(dp[i-1]) 加上字符串 subs 前面的有效字符串(dp[i - dp[i - 1] - 2]) 加上 2，这时候字符串可以形如"(...)((...))" 。 3.确定边界条件 和 初始情况：
i-2 有可能小于0而导致越界，这时候就是只有()，前面记为0就好了i - dp[i - 1] - 2 和 i - dp[i - 1] - 1 都有可能出现小于0的越界问题，如果越界了 同样 记为0即可
-解题代码
class Solution { public: int longestValidParentheses(string s) { int len = s.size(); int ans = 0; vector<int> dp(len); for(int i = 1; i < len; i++) { if (s[i] == ')') { if (s[i-1] == '(') { dp[i] = (i - 2 >= 0 ? dp[i-2] : 0) + 2; } else if (i - dp[i-1] - 1 >= 0 && s[i-dp[i-1]-1] == '(') { dp[i] = (i - dp[i-1] - 2 >=0 ? dp[i-dp[i-1]-2] : 0) + dp[i-1] + 2; } } ans = max(ans, dp[i]); } return ans; } };结果
