LeetCode短视频 | 最长有效括号使用栈很容易解决，但偏用动态规划

http://mpvideo.qpic.cn/0a78hc3fzq2vabiobqgq4cqkb4hvxugkwf6dmnzlbacq4cqebiba.f10002.mp4?dis_k=f780d4c9bb0935e21e45291788083d25&dis_t=1577419912

题目如下：

看了这个题目的标签，动态规划是其的标签之一。这题目我第一反应可以使用栈来解决，但我们偏用动态规划看看解决的是什么样子的。

我们定义一个dp[i]数组，其中i表示字符串的下标，值是目前有效的子字符串。

我们将dp数组全部初始化为0。

现在，很明显有效的子字符串一定以‘)’结尾。

我们可以进一步得出结论：以‘(’的子字符串对应位置上的值必定为0。

所以说我们只需要更新‘)’在dp数组中对应位置的值。

为了求出dp数组，我们每两个字符检查一次，如果满足如下条件

s[i]=‘)’且s[i−1]=‘(’，形如‘‘…()..."，可以推出：dp[i]=dp[i−2]+2

可以进行这样的转移，是因为结束部分的"()"是一个有效子字符串，并且将之前有效子字符串的长度增加了2。

s[i]=‘)’且s[i−1]=‘)’，也就是字符串形如‘‘...))..."，我们可以推出：

如果s[i−dp[i−1]−1]=‘(’，则dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2

这背后的原因是如果倒数第二个‘)’是一个有效子字符串的一部分（记为s），对于最后一个‘)’，如果它是一个更长子字符串的一部分，那么它一定有一个对应的‘(’，它的位置在倒数第二个‘)’所在的有效子字符串(s)的前面。

因此，如果子字符串s的前面恰好是‘(’，那么我们就用2加上s的长度（dp[i−1]）去更新dp[i]。

除此以外，我们也会把有效子字符串‘‘(,s,)"之前的有效子字符串的长度也加上，dp[i−dp[i−1]−2]。

Java代码：

——END——