🚀 C++ 动态规划：有效括号嵌套深度详解

🌐 问题背景

给定一个由 ‘(‘ 和 ‘)’ 组成的字符串，计算该字符串的有效括号嵌套深度。有效括号嵌套深度是指最深的有效括号对的层数。

示例

• 输入："(()())"
  输出：2
  解释：最深的有效括号对是 "(())"，嵌套深度为 2。
• 输入："((()))"
  输出：3
  解释：最深的有效括号对是 "((()))"，嵌套深度为 3。

🛠️ 动态规划解法

1. 定义状态

我们定义一个数组 dp，其中 dp[i] 表示前 i 个字符的最大嵌套深度。

2. 状态转移方程

• 如果当前字符是左括号 '('，则 dp[i] = dp[i-1] + 1。
• 如果当前字符是右括号 ')'，则 dp[i] = max(dp[i-1], dp[match(i)] + 1)，其中 match(i) 是与当前右括号匹配的左括号的位置。

3. 初始化

• dp[0] = 0，因为第一个字符之前的嵌套深度为 0。

4. 实现代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int maxDepth(string s) {
    int n = s.size();
    vector<int> dp(n, 0);
    stack<int> stk;

    for (int i = 0; i < n; ++i) {
        if (s[i] == '(') {
            stk.push(i);
        } else if (s[i] == ')' && !stk.empty()) {
            int match = stk.top();
            stk.pop();
            dp[i] = match > 0 ? dp[match - 1] + 1 : 1;
            if (i > 0) {
                dp[i] = max(dp[i], dp[i - 1]);
            }
        }
    }

    return dp[n - 1];
}

int main() {
    string s = "(()())";
    cout << "最大嵌套深度: " << maxDepth(s) << endl;
    return 0;
}

5. 代码解释

• 栈的使用：我们使用栈来记录左括号的位置，当遇到右括号时，从栈中弹出最近的一个左括号，计算当前的嵌套深度。
• 动态规划数组：dp[i] 记录前 i 个字符的最大嵌套深度。
• 状态转移：根据当前字符是左括号还是右括号，更新 dp 数组。

🛑 常见问题及解决方案

问题1：输入字符串中包含非法字符

解决方案：

• 过滤非法字符：在处理字符串之前，过滤掉所有非括号字符。
• 使用正则表达式：使用正则表达式匹配和替换非法字符。

问题2：栈为空时遇到右括号

解决方案：

• 忽略无效括号：如果栈为空时遇到右括号，说明这是一个无效的括号，可以直接忽略。
• 记录错误位置：记录无效括号的位置，便于后续调试。

问题3：嵌套深度计算错误

解决方案：

• 检查状态转移方程：确保状态转移方程正确，特别是 dp[i] = max(dp[i-1], dp[match(i)] + 1) 这一部分。
• 调试输出：在代码中添加调试输出，查看中间结果，找出问题所在。

问题4：性能问题

解决方案：

• 优化栈操作：减少不必要的栈操作，提高性能。
• 使用数组替代栈：如果括号数量较少，可以使用数组替代栈，减少内存开销。

问题5：边界条件处理

解决方案：

• 初始化：确保 dp 数组的初始值正确，特别是 dp[0]。
• 特殊情况处理：处理空字符串、单个括号等特殊情况，确保代码的鲁棒性。

🎓 结论

通过本文的介绍，你应该已经了解了如何使用动态规划解决有效括号嵌套深度的问题。无论是状态定义、状态转移方程还是实现代码，都有详细的解释和示例。希望这些知识能帮助你在实际开发和竞赛中更好地解决括号匹配问题！

---

如果你有任何疑问或需要进一步的帮助，请在评论区留言。期待与你交流！🌟