题解 | #最长的括号子串#

用dp来解，设dp[i]为以第i个字符为结尾的最长匹配括号序列。

状态转移方程为：

$ifs[i+1]+s[i]={=}^{\mathrm{\prime }}({)}^{\mathrm{\prime }},dp[i+1]=dp[i-2]+2if\; \backslash \; s[i+1]+s[i]==\text{'}()\text{'},dp[i+1]=dp[i-2]+2$ （1）

$ifs[i+1]+s[i]!{=}^{\mathrm{\prime }}({)}^{\mathrm{\prime }}anddp[i]=0,dp[i+1]=0if\; \backslash \; s[i+1]+s[i]!=\text{'}()\text{'}\; \backslash \; and\; \backslash \; dp[i]=0,dp[i+1]=0$ （2）

$ifs[i+1]+s[i]!{=}^{\mathrm{\prime }}({)}^{\mathrm{\prime }}anddp[i]>=0ands[i-dp[i]]+s[i+1]={=}^{\mathrm{\prime }}({)}^{\mathrm{\prime }},dp[i+1]=dp[i]+dp[i-1-dp[i]]+2if\; \backslash \; s[i+1]+s[i]!=\text{'}()\text{'}\; \backslash \; and\; \backslash \; dp[i]>=0\; \backslash \; and\; \backslash \; s[i-dp[i]]+s[i+1]==\text{'}()\text{'},dp[i+1]=dp[i]+dp[i-1-dp[i]]+2$ （3）

一次性要完全写对状态转移方程是有点难，可以在测试过程中改进，比如第三个状态转移方程我就是看了错误的case才改进出来的，刚开始没想到还要加上dp[i-1-dp[i]]。代码的话就容易了

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return int整型
#
class Solution:
    def longestValidParentheses(self , s: str) -> int:
        # write code here
        if len(s)==0:
            return 0
        # 初始化dp
        dp = [0]*len(s)
        for i in range(1 , len(s)):
            if s[i-1:i+1] == '()':
                if i >=2:
                    dp[i] = 2+dp[i-2]
                else:
                    dp[i] = 2
            elif dp[i-1]==0:
                dp[i]=0
            else:
                if s[i-1-dp[i-1]] + s[i] == '()':
                    dp[i] = dp[i-1] + dp[i-2-dp[i-1]] + 2
                else:
                    dp[i] = 0
        print(dp)
        return max(dp)


s = "()(())"
print(Solution().longestValidParentheses(s))