优化动态规划：最长有效括号与最大子序和

在本文档中，主要讨论了与动态规划相关的两个LeetCode题目：正则表达式匹配和最长有效括号问题。首先，对于Q10正则表达式匹配，虽然未给出具体实现，但可以推测是考察如何使用动态规划或者状态转移来处理字符串中的匹配规则。 在Q32最长有效括号问题中，作者提出了两种解决策略： 1. 方法1（基于子串状态）：通过定义dp[i][j] = k表示子串i到j，其中k表示左括号与右括号的数量差。当k为-1时，表示子串非法；k为正数表示可能有后续合法括号。这种方法直观易懂，但时间复杂度较高，为O(n^2)。 2. 方法2（双指针法）：针对左括号数量m大于等于右括号数量n的情况，采用双向遍历。当发现m等于n时，说明找到了一个有效括号对，记录下当前长度。如果m小于n，则重置子串范围到下一个位置，并继续查找。这种方法优化了时间复杂度，但需要对每个位置的括号进行状态更新。 另外，还介绍了如何用动态规划求解Q53的最大子序和问题。这里有两个解决方案： - 动态规划：定义f(i)为以元素ai结尾的最大子序和，状态转移方程为f(i) = max(f(i-1)+ai, ai)，并使用滚动数组（空间复杂度为o(1)）来压缩空间。 - 滑动窗口：通过维护一个滑动窗口，计算当前窗口和sum，判断当sum <= 0时，扩展窗口没有价值，应舍弃当前子数组并更新sum和ans。只有当sum > 0时，窗口和才有贡献。 总结来说，文档涵盖了动态规划在字符串处理和数值序列分析中的应用，特别是括号匹配和子序列和问题的高效算法设计。理解并掌握这些方法对于提高动态规划在实际问题中的运用能力非常关键。