【Hot 100 刷题计划】 LeetCode 32. 最长有效括号 | C++ 动态规划严密推导 (Hard)

LeetCode 32. 最长有效括号

📌 题目描述

题目级别：困难

给你一个只包含'('和')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。

• 示例 1:
  输入：s = "(()"
  输出：2
  解释：最长有效括号子串是"()"

• 示例 2:
  输入：s = ")()())"
  输出：4
  解释：最长有效括号子串是"()()"

💡 破题思路：动态规划 (跨越与拼接)

这道题用动态规划解，难点在于状态转移时的嵌套问题。

状态定义：
定义dp[i]为：以s[i]字符结尾的最长有效括号子串的长度。
(显然，如果s[i]是'('，它绝不可能是一个有效括号的结尾，所以dp[i]直接为 0。我们只需要关心s[i] == ')'的情况)。

状态转移方程：
当s[i] == ')'时，有两种情况：

1. 相邻匹配 (s[i - 1] == '(')：
   例如...()。这组成了一个新的基础对，长度加 2。同时要接上它前面的有效长度。

   dp[i] = dp[i - 2] + 2

2. 嵌套匹配 (s[i - 1] == ')')：
   例如...))。这意味着我们要跨越前面已经匹配好的内部括号，去前面找有没有剩下的左括号。
   前面内部括号的长度是dp[i - 1]。我们跳过这段长度，检查字符s[i - dp[i - 1] - 1]是否是'('。
   如果是，说明我们找到了匹配！不仅要加上内部长度dp[i - 1]和新配对的 2，还要接上这个配对前面可能连着的有效长度dp[i - dp[i - 1] - 2]。

   dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]

💻 C++ 代码实现 (DP 法)

classSolution{public:intlongestValidParentheses(string s){intn=s.size();if(n<2)return0;intdp[n+10];memset(dp,0,sizeofdp);intres=0;for(inti=1;i<n;i++){if(s[i]==')'){// 情况1：相邻匹配 "()"if(s[i-1]=='('){if(i>=2)dp[i]=dp[i-2]+2;elsedp[i]=2;}// 情况2：嵌套匹配 "))"elseif(s[i-1]==')'){// i - dp[i - 1] - 1 就是跳过内部有效括号后，前面那个待匹配字符的下标if(i-dp[i-1]-1>=0&&s[i-dp[i-1]-1]=='('){// 如果再往前还有有效括号，一起拼接起来if(i-dp[i-1]-2>=0)dp[i]=dp[i-dp[i-1]-2]+dp[i-1]+2;elsedp[i]=dp[i-1]+2;}}}res=max(res,dp[i]);}returnres;}};