【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] )时有两种情况相邻匹配 (s[i - 1] ()例如...()。这组成了一个新的基础对长度加 2。同时要接上它前面的有效长度。dp[i] dp[i - 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){intns.size();if(n2)return0;intdp[n10];memset(dp,0,sizeofdp);intres0;for(inti1;in;i){if(s[i])){// 情况1相邻匹配 ()if(s[i-1](){if(i2)dp[i]dp[i-2]2;elsedp[i]2;}// 情况2嵌套匹配 ))elseif(s[i-1])){// i - dp[i - 1] - 1 就是跳过内部有效括号后前面那个待匹配字符的下标if(i-dp[i-1]-10s[i-dp[i-1]-1](){// 如果再往前还有有效括号一起拼接起来if(i-dp[i-1]-20)dp[i]dp[i-dp[i-1]-2]dp[i-1]2;elsedp[i]dp[i-1]2;}}}resmax(res,dp[i]);}returnres;}};