32. 最长有效括号

标签：题解 32 括号 text answer 最长 dp

题目链接	32. 最长有效括号
思路	动态规划
题解链接	官方题解
关键点	1. 只有\(s_{i}=\text{(}\)时才需要转移 2. 当遇到'...))'格式的情形时，需要考虑前面片段中转移的索引下标
时间复杂度	\(O(n)\)
空间复杂度	\(O(n)\)

状态转移方程为（只有\(s_{i}=\text{(}\)时才需要转移）：

\[dp_{i} = \begin{cases} 2 + dp_{i-2}, &\quad s_{i-1}=\text{(} \\ 2 + dp_{i-1} + dp[i-1-dp[i-1]-1], &\quad s_{i-1} = \text{) and } s_{i-1-dp_{i-1}} = \text{(} \end{cases} \]

代码实现：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        answer = 0

        n = len(s)
        dp = [0] * n
        for i in range(1, n):
            if s[i] == ')':
                if s[i-1] == '(':
                    dp[i] = 2 + (0 if i<2 else dp[i-2])
                elif i - dp[i-1] > 0 and s[i-1 - dp[i-1]] == '(':
                    dp[i] = 2 + dp[i-1] + (0 if i-dp[i-1] < 2 else dp[i-1-dp[i-1]-1])
                answer = max(answer, dp[i])

        return answer

标签：题解,32,括号,text,answer,最长,dp
From： https://www.cnblogs.com/WrRan/p/18413109