题目链接

关键词

解析

动态规划

• 状态定义：定义 dp[i] 为以 s[i] 结尾的最长有效括号子串的长度

• 状态方程：
• 如果第 i - 1 个字符可以匹配，就从 i - 1 转移过滤
• 如果第 i - 1 个字符不可以匹配，就从 i - dp[i - 1] 转移过来

栈模拟

计数统计

• 按照括号匹配的计数思路，用两个变量，分别记录左括号和右括号的数量，如果两个括号数量相等，就另结果 +2，如果右括号比左括号还多，就说明不合法，重新计数

• 上面的做法，只能统计出一个方向的最大结果，所以需要反方向再统计一遍

代码

动态规划

栈模拟

计数统计，但是正负各一次

相似题目