1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
我们先看第 i 个位置，这个位置的元素 *s[i]*可能有如下两种情况：
s[i] == '(' :
这时，s[i] 无法和其之前的元素组成有效的括号对，所以，dp[i] = 0
s[i] == ')' :
这时，需要看其前面对元素来判断是否有有效括号对。
情况1:
s[i - 1] == '('
即 s[i] 和 s[i - 1] 组成一对有效括号，有效括号长度新增长度2，i位置对最长有效括号长度为 其之前2个位置的最长括号长度加上当前位置新增的2，我们无需知道i-2位置对字符是否可以组成有效括号对。
那么有：
dp[i] = dp[i - 2] + 2
2020041743046png
情况2:
s[i - 1] == ')'
这种情况下，如果前面有和s[i]组成有效括号对的字符，即形如( (....) )，这样的话，就要求*s[i - 1]位置必然是有效的括号对，否则s[i]*无法和前面对字符组成有效括号对。
这时，我们只需要找到和*s[i]*配对对位置，并判断其是否是 ( 即可。和其配对对位置为：i - dp[i - 1] - 1。
如果：s[i - dp[i - 1] - 1] == '(' :
有效括号长度新增长度2，i位置对最长有效括号长度为 i-1位置的最长括号长度加上当前位置新增的2，那么有：
dp[i] = dp[i - 1] + 2
值得注意的是，i - dp[i - 1] - 1 和 i 组成了有效括号对，这将是一段独立的有效括号序列，如果之前的子序列是形如 (...) 这种序列，那么当前位置的最长有效括号长度还需要加上这一段。所以：
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
注： 这个在分析时是很容易遗漏的，分析要更细致。我在第一次分析是就遗漏了，提交后，有用例 )()(()))不过，分析后发现是少了这一段。
2020041742634png
子问题：
根据上面的分析，我们得到了如下两个计算公式：
dp[i] = dp[i - 2] + 2
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
那么，求dp[i]就变成了求dp[i - 1]、 dp[i - 2]、*dp[i - dp[i - 1] - 2]*的子问题。
这样状态也明确了：
设dp 数组，其中第 i 个元素表示以下标为 i 的字符结尾的最长有效子字符串的长度。**
转移方程：
子问题明确后，转移方程直接由子问题得到：
if s[i] == '(' :
dp[i] = 0
if s[i] == ')' :
if s[i - 1] == '(' :
dp[i] = dp[i - 2] + 2 #要保证i - 2 >= 0
if s[i - 1] == ')' and s[i - dp[i - 1] - 1] == '(' :
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 #要保证i - dp[i - 1] - 2 >= 0
初始条件和边界情况：
初始条件： dp[i] = 0
边界情况：需要保证计算过程中：i - 2 >= 0 和 i - dp[i - 1] - 2 >= 0
计算顺序：
无论第一个字符是什么，都有：dp[0] = 0
然后依次计算：dp[1], dp[2], ..., dp[n - 1]
结果是： max(dp[i])
|