32 Longest Valid Parentheses
动态规划的方法： 使用一个dp数组，第i位存储以第i位为结尾的最长的匹配字符串长度。这样的话，很明显，只有以")"结尾，才有可能是匹配字符串的末尾，因此，我们将所有"("对应的位置的dp值定义为0，同时只更新")"处的dp数值。
动态规划的递归计算方法：
- 如果当前是")", 并且上一个元素是”(“，那么dp[i] = dp[i-2]+2
- 如果当前是")", 并且上一个元素是”)“，如果s[i-dp[i-1]-1] == '(' 那么dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
if s == "":
return 0
length = len(s)
dp = [0 for i in range(length)]
for i in range(length):
if s[i] == "(":
dp[i] = 0
if length >= 2:
dp[1] = 2 if s[:2] == "()" else 0
for i in range(2, length):
if s[i] == "(":
dp[i] = 0
else:
if s[i-1] == "(":
dp[i] = dp[i-2] + 2
if s[i-1] == ")" and i-dp[i-1]-1 >=0 and s[i-dp[i-1]-1] == "(":
dp[i] = dp[i-1] + dp[i-dp[i-1] - 2] + 2
return max(dp)