动态规划的重点推导出状态转移方程

最长有效括号

题目描述题解-初步理解题解-更进一步题解-最终推导代码实现另一种神奇而被人喜欢的方法

题目描述

先来看下这个题目描述：

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。 示例 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”

参阅官方题解中「方法2-动态规划」

题解-初步理解

初始化dp数组，dp[0]*len(s)dp[i]表示以该位元素结尾的最长有效子字符串的长度在遍历字符串的时候，只要该位是左括号，就保持dp[i] = 0从后向前推导dp之间的状态转移方程，假设我们现在位于i == 5 更新i = 4的位置为2接下来要判断位是有效子括号对前面那位，即i = 2，发现这也是一对有效子括号 那么与5对应的左括号一定不在这个有效对中咯，继续向前寻找，发现dp[0]=0，所以最终有效括号即为这两对dp[2]+dp[4]=4

这个示例没有找到前面所对应的与最后一位匹配的左括号，但是可以帮助我们先理解状态数组，以及如何寻找与i对应的位置，即减去内部的有效子串dp[i-1]，我们再看一个示例：

题解-更进一步

“()((())”

初始化这个dp数组，先填入不「镶嵌」的有效子括号对。

现在我们来观察i = 3，已知基础长度为2，更新dp[6]为2在上一状态中，我们知道i = 3和i =6中还夹了一对有效子串，并存储在i = 5中，因此 dp[i] = 2 + dp[i-1]，因此dp[5]更新为4. i = 2时为0，因此i = 6保持不变，依然为4。

题解-最终推导

现在来看当查找外部时为右括号的情况

“()(())”

状态转移方程变成 dp[i] = 2 + dp[i-1] + dp[i-dp[i-1]-2]我们用这个方程求解一下dp[1] dp[1] = 2 + dp[0] + dp[1-dp[0]-2] = 2 + 0 + dp[-1] dp[-1]不存在，因此为0，最后dp[1] = 2你以为结束了么？No，这里存在一个问题，就是在python中dp[-2]是倒数第2个元素，本例中dp[-2] = 2所以我们要加入一个限制条件，即被查找元素的值一定要大于等于0

代码实现

class Solution2: """动态规划 i-dp[i-1]-1是与当前）对称的位置""" def longestValidParentheses(self, s: str) -> int: n = len(s) if n == 0: return 0 dp = [0]*n for i in range(len(s)): if s[i] == ')' and i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1]=='(': dp[i] = 2 + dp[i-1] + dp[i-dp[i-1]-2] return max(dp)

另一种神奇而被人喜欢的方法

虽然动态规划很厉害，但我个人还是很喜欢方法4…

class Solution4: """正向逆向相结合的方法 当右括号个数 > 左括号个数的时候，直接将"左括号个数"、"右括号个数"重新初始化为0 逆向遍历时，当右括号 < 左括号个数，直接将"左括号个数"、"右括号个数"重新初始化为0 时间复杂度O(N)，空间复杂度O(1) """ def longestValidParentheses(self, s: str) -> int: n, left, right, maxlength = len(s), 0, 0, 0 # 正序遍历 for i in range(n): if s[i] == '(': left += 1 else: right += 1 if left == right: maxlength = max(maxlength,2*right) elif right > left: left = right = 0 # 反序遍历 left = right = 0 for i in range(n-1,-1,-1): if s[i] == '(': left += 1 else: right += 1 if left == right: maxlength = max(maxlength,2*left) elif right < left: left = right = 0 return maxlength

感觉就是思考能简单则简单哈哈