一、32. 最长有效括号（Longest Valid Parentheses）
题目难度：Hard
🔗 题目链接
32. 最长有效括号 - 力扣（LeetCode）
📝 题目描述
给你一个只包含'('和')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：
s = "(()"
输出：2
解释：最长有效括号子串是"()"
示例 2：
输入：
s = ")()())"
输出：4
解释：最长有效括号子串是"()()"
示例 3：
输入：
s = ""
输出：0
🧠 思路分析
有效括号匹配类问题，可以归纳为一维DP的典型应用。
1. 状态定义
设dp[i]表示以s[i]字符结尾的最长有效括号子串的长度。由于左括号无法作为有效子串的结尾，dp[i]在s[i] == ')'时无意义，因此主要关注右括号的情况。
2. 转移方程推导 —— 分类讨论
Case 1：形如
...()—— 直接与前一个字符配对
若s[i-1] == '('，则s[i-1]和s[i]构成一个有效括号对()，此时：dp[i] = dp[i-2] + 2
这意味着"()"直接粘在前一个有效括号子串后面，将两段有效括号拼接起来。Case 2：形如
...((...))—— 嵌套匹配
若s[i-1] == ')'，此时前面的内容处于嵌套状态。计算公式为：先计算出
i - dp[i-1] - 1，定位与当前)配对的(的位置。若配对成功，还需额外加上该
(前面的有效长度，因此：dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]（下标越界时按 0 处理）。
举例说明：对于s = "(()())"，末尾字符(s[5] = ')')与前一个字符(s[4] = ')')之间实际上是一个内部已完美匹配的"()"（长度为 2），再向外剥开一层括号，内部长度 4 加上"()"的 2 就构成了完整的 6。
💻 代码实现（C++）
class Solution { public: int longestValidParentheses(string s) { int n = s.size(); if (n <= 1) return 0; vector<int> dp(n, 0); int maxLength = 0; // 遍历从索引 1 开始，因为 dp[0] 要么是 0 要么无意义 for (int i = 1; i < n; ++i) { // 只有右括号才可能形成有效括号 if (s[i] == ')') { // Case 1: ...() 形式 if (s[i - 1] == '(') { dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } // Case 2: ...)) 形式（嵌套匹配） else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') { int matchedIndex = i - dp[i - 1] - 1; int prev = (matchedIndex >= 1 ? dp[matchedIndex - 1] : 0); dp[i] = dp[i - 1] + 2 + prev; } maxLength = max(maxLength, dp[i]); } } return maxLength; } };📚 相关学习资源
LeetCode 32. 最长有效括号（栈解法，含基准下标技巧） （技术社区 · 2025-11-17）
使用 d p 数组细致讲解动态规划原理，包含状态定义与两种匹配情况详解。LeetCode 32. 最长有效括号（动态规划） （技术社区 · 2025-03-20）
分两类递推式，结合示例"(()())"详细推演整个匹配过程，代码逻辑均做了深入剖析。
⏱ 复杂度分析
时间复杂度：
O(n)，仅需一次遍历。空间复杂度：
O(n)，用于存储 DP 数组。
二、312. 戳气球（Burst Balloons）
题目难度：Hard
🔗 题目链接
312. 戳气球 - 力扣（LeetCode）
📝 题目描述
有n个气球，编号为0到n-1，每个气球上都标有一个数字，这些数字存在数组nums中。现在要求你戳破所有的气球。每当你戳破一个气球i时，你可以获得nums[left] * nums[i] * nums[right]个硬币。这里的left和right代表和i相邻的两个气球的序号。如果i - 1或i + 1超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例：
输入：
nums = [3,1,5,8]
输出：167
解释：nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []coins = 3·1·5 + 3·5·8 + 1·3·8 + 1·8·1 = 167
🧠 思路分析
「戳气球」的难度不在代码本身，而在于如何定义子问题。
1. 为什么“正着思考”是陷阱？
如果正向考虑“先戳哪个气球”，戳破后左右邻居会立即变成新的邻居，后续戳的收益取决于前面的选择，子问题之间产生了耦合，状态无法独立转移。
2. 逆向思考（区间 DP 关键）
定义dp[i][j]表示：戳破开区间(i, j)内所有气球能得到的最大硬币数，注意i和j本身不被戳破，它们只是作为“边界”存在。
为了计算dp[i][j]，我们枚举这个开区间内最后一个被戳破的气球k（满足i < k < j）。当k是最后一个被戳破时，它的左右邻居是i和j（因为在戳k之前，区间(i, k)和(k, j)所有的气球已经被戳光了），戳破k的得分是nums[i] * nums[k] * nums[j]。
因此状态转移方程为：dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])，其中i < k < j。
3. 预处理技巧
为了方便处理边界，在nums数组的开头和结尾分别插入一个值为1的虚拟气球。
💻 代码实现（C++）
class Solution { public: int maxCoins(vector<int>& nums) { int n = nums.size(); // 在数组两端插入 1，作为虚拟气球 vector<int> points(n + 2, 1); for (int i = 1; i <= n; ++i) { points[i] = nums[i - 1]; } // dp[i][j] 表示戳破开区间 (i, j) 内所有气球的最大硬币数 vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0)); // 按区间长度递增的顺序填表 for (int len = 2; len <= n + 1; ++len) { for (int i = 0; i + len <= n + 1; ++i) { int j = i + len; for (int k = i + 1; k < j; ++k) { dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + points[i] * points[k] * points[j]); } } } return dp[0][n + 1]; } };📚 相关学习资源
经典动态规划：戳气球（区间 DP 逆向思考，图文并茂）
文章从“为什么正向不行”切入，深入讲解如何联想到“逆向”的 DP 模型，逐步推导状态转移方程，并包含多语言代码。动态规划的终极博弈：逆向思考，引爆「戳气球」
回溯思路 + 区间 DP 详解，专门讨论如何定义 “最后一步” 完成状态转移。力扣hot100 · 312. 戳气球（区间 DP 详解） — 技术社区涵盖区间 DP 的推导过程，包含完整的、可供直接运行的 C++ 代码与测试用例。
⏱ 复杂度分析
时间复杂度：
O(n³)，三层循环（区间长度 + 区间起点 + 枚举最后戳破的气球）。空间复杂度：
O(n²)，用于存储dp表。
三、10. 正则表达式匹配（Regular Expression Matching）
题目难度：Hard
🔗 题目链接
10. 正则表达式匹配 - 力扣（LeetCode）
📝 题目描述
给你一个字符串s和一个字符规律p，请你来实现一个支持'.'和'*'的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要覆盖整个字符串s的，而不是部分匹配。
示例：
输入：
s = "aa",p = "a"
输出：false（"a" 无法匹配 "aa" 整个字符串）
输入：
s = "aa",p = "a*"
输出：true（'*'代表可以匹配零个或多个前面的 "a"，因此 "a*" 可以匹配 "aa"）
输入：
s = "ab",p = ".*"
输出：true（".*"表示匹配任意字符序列）
🧠 思路分析
正则表达式匹配是一道二维DP的经典问题。
1. 状态定义
设dp[i][j]表示：字符串s的前i个字符能否匹配模式p的前j个字符。
2. 转移方程
如果
p[j-1]是普通字母或'.'（不含*）：
必须让s[i-1]匹配p[j-1]（字符相同或p[j-1]为'.'），然后看前面的部分是否匹配，即：dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.')如果
p[j-1] == '*'（注意*必须跟在某个字符后面，比如p[j-2]为匹配符或字母）：
此时有两种可能性：匹配 0 次：让
*直接“消失”，丢掉p[j-2]这个字符和*，即dp[i][j] = dp[i][j-2]。匹配 1 次或多次：前提是
s[i-1]能够匹配p[j-2]；匹配成功后，模式中的p[j-2]*可继续匹配s的更多字符，即dp[i][j] = dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')
3. 初始化
dp[0][0] = true（空字符串匹配空模式）dp[0][j]：若p[j-1] == '*'，则dp[0][j] = dp[0][j-2]（比如"a*b*"可以匹配空串）
💻 代码实现（C++）
class Solution { public: bool isMatch(string s, string p) { int m = s.length(), n = p.length(); vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false)); dp[0][0] = true; // 处理空串与 "a*b*" 类模式匹配 for (int j = 1; j <= n; ++j) { if (p[j - 1] == '*') { dp[0][j] = dp[0][j - 2]; } } // 填充 dp 表 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (p[j - 1] == s[i - 1] || p[j - 1] == '.') { dp[i][j] = dp[i - 1][j - 1]; } else if (p[j - 1] == '*') { // 匹配零次（跳过 x*） dp[i][j] = dp[i][j - 2]; // 匹配一次或多次 if (p[j - 2] == s[i - 1] || p[j - 2] == '.') { dp[i][j] = dp[i][j] || dp[i - 1][j]; } } } } return dp[m][n]; } };📚 相关学习资源
Leetcode-10.正则表达式匹配（暴力递归 + 记忆化搜索） — 技术社区
力扣热题100实战 · 正则表达式匹配（动态规划，递归） — CSDN
Classic DP: Regular Expression Matching（英） — labuladong
⏱ 复杂度分析
时间复杂度：
O(m·n)，其中m为s的长度，n为p的长度。空间复杂度：
O(m·n)，DP 网格存储。
四、115. 不同的子序列（Distinct Subsequences）
题目难度：Hard
🔗 题目链接
115. 不同的子序列 - 力扣（LeetCode）
📝 题目描述
给定一个字符串s和一个字符串t，计算在s的子序列中t出现的个数。字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。
示例：
输入：
s = "rabbbit", t = "rabbit"
输出：3
解释：如下图所示，有 3 种s的子序列构成"rabbit"：
ra b b b i t → ra b1 b2 i t
ra b b b i t → ra b1 b3 i t
ra b b b i t → ra b2 b3 i t
🧠 思路分析
不同子序列问题的核心在于处理重复字符的贡献，这非常贴合二维计数 DP的场景。
1. 状态定义
设dp[i][j]表示：源字符串s的前i个字符（s[0...i-1]）中，目标字符串t的前j个字符出现的子序列个数。
2. 转移方程（两种源）
对于当前要填的格dp[i][j]，聚焦于最后一个字符s[i-1]：
不使用
s[i-1]匹配（无论字符是否相同，我们都可以选择跳过它）：dp[i][j] = dp[i-1][j]
即组建t的前j个字符完全依赖s的前i-1个字符。使用
s[i-1]匹配t[j-1]（仅在s[i-1] == t[j-1]时成立）：dp[i][j] = dp[i-1][j-1]
因为一旦使用该字符，就消耗掉了t的最末字符，其余部分由s的前i-1个字符去匹配t的前j-1个字符。综合起来，如果
s[i-1] == t[j-1]，则dp[i][j] = dp[i-1][j] + dp[i-1][j-1]；否则dp[i][j] = dp[i-1][j]。
3. 初始化
dp[i][0] = 1（空字符串是任何字符串的子序列，只有 1 种方式）dp[0][j] = 0(j > 0)（空字符串无法匹配非空目标）
💻 代码实现（C++）
class Solution { public: int numDistinct(string s, string t) { int m = s.length(), n = t.length(); if (m < n) return 0; unsigned long long INF = 1e18; // 防止溢出 vector<vector<unsigned long long>> dp(m + 1, vector<unsigned long long>(n + 1, 0)); // 初始化，dp[i][0] = 1 for (int i = 0; i <= m; ++i) dp[i][0] = 1; // 填充 dp 表 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { dp[i][j] = dp[i - 1][j]; if (s[i - 1] == t[j - 1]) { dp[i][j] += dp[i - 1][j - 1]; } if (dp[i][j] >= INF) dp[i][j] = INF; // 防止结果巨大导致的溢出 } } return (int)dp[m][n]; } };📚 相关学习资源
代码随想录 115.不同的子序列（动规五部曲完整解析） — 技术社区
动态规划的“计数”魔法：不同的子序列（多语言推导） — CSDN
代码随想录 · LeetCode115不同的子序列（含视频讲解） — CSDN
⏱ 复杂度分析
时间复杂度：
O(m·n)，两层循环。空间复杂度：
O(m·n)，DP 表存储。
结语
高级动态规划篇的四道题覆盖了 DP 的多个关键维度和递推模式：
最长有效括号：一维 DP + 分类讨论，直击子串匹配时的递推与特殊边界。
戳气球：区间 DP 的经典例题，“逆向思维” 解决前后依赖。
正则表达式匹配：二维 DP 的“匹配 +
*分支”综合应用。不同的子序列：二维计数 DP，统计匹配的数量而非布尔值。
这四个题综合了 DP 的最优性（最大/最小）、可行性（布尔判断）和计数（累加）三大类型，是面试中高阶 DP 模块的必刷题。
下一篇预告：LeetCode 热题 100 精讲｜图遍历基础篇：岛屿数量（BFS/DFS） · 腐烂的橘子（多源 BFS） · 课程表（拓扑排序） · 课程表 II（拓扑排序输出），持续更新连载。
免责声明
本文仅供学习交流与算法思路分享，内容基于作者个人理解及公开资料整理。所有题目链接、资源文档均来源于互联网，版权归原作者所有。文章中的代码已在常见环境下验证，但不同环境或版本可能导致结果差异，请读者自行测试并谨慎参考。如有疑问或版权问题，请联系作者处理。
